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.

Link to paper