Complezity 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.
Anne Condon Jan Manuch Chris Thachuk
University of British Columbia, Vancouver BC V6T 1Z4, Canada Simon Fraser University, Burnaby BC V5A 1S7, Canada
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
265-275
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）