A Graph-Based Approach for the DNA Word Design Problem

The aim of this paper is to improve the best known solution of an important problem, the DNA Word Design problem, which has its roots in Bioinformatics and Coding Theory. The problem is to design DNA codes that satisfy some combinatorial constraints. The constraints considered are: minimum Hamming distance, fixed GC content and the reverse complement Hamming distance. The problem is modeled as a maximum independent set problem. Existing complex approaches for the maximum independent set problem, suitable for large graphs, were tested. In order to tackle large instances, libraries for external memory computations and sampling techniques were investigated. Eventually, we succeed in finding good lower bounds for the instances that were analyzed.