Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis
Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis
复制标题
碰撞感知字符串划分问题的复杂性及其与基因合成寡核苷酸设计的关系
DOI：
10.1007/978-3-540-69733-6_27
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Chris Thachuk
中科院分区：
文献类型：
--
作者：
A. Condon;Ján Manuch;Chris Thachuk
长基因和整个基因组的人工合成是通过DNA寡聚片段的自组装来实现的，DNA寡聚片段足够短，可以使用DNA合成仪生成。给定待合成的双链体的描述，计算挑战是选择短寡核苷酸，使得一旦合成，它们将无错误地自组装。在本文中，我们表明，这个问题的一个自然的抽象，碰撞感知字符串分割问题，是NP完全的。
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.