Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis

摘要

Artificial synthesis of long genes and entire genomes is achieved by self-assembly of DNA oligo fragments - fragments which are short enough to be generated using a DNA synthesizer. Given a description of the duplex to be synthesized, a computational challenge is to select the short oligos so that, once synthesized, they will self-assemble without error. In this paper, we show that a natural abstraction of this problem, the collision-aware string partition problem, is NP-complete.