|Title:||Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis|
Deparment of COmputer Science, UBC
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.