General nucleic acid sequence design using implicit enumeration

The design of DNA and RNA sequences is an important area of research in fields such as gene microarrays, gene chips, medical diagnostic, and biomolecular computing. These nucleic acid molecules must satisfy several combinatorial, thermodynamic and secondary structure constraints, which aim to avoid undesired hybridizations and make the molecular experiment more reliable. In this paper, we formulate the DNA sequence design as a multiobjective optimization problem and solving it using implicit enumeration search approach. To heuristically search for good strand sets, our algorithm considers groups of solutions together. If any partial solution violates any constraint, all completion of this partial solution should be excluded from further consideration which accelerate the convergent of our algorithm. Finally, the performance of our algorithm is compared with other sequence design methods, and the results show that the implicit enumeration algorithm outperforms in DNA sequences quality, quantity and efficiency.