On the Computational Complexity of Tile Set Synthesis for DNA Self-Assembly
On the Computational Complexity of Tile Set Synthesis for DNA Self-Assembly
复制标题
DNA自组装瓦片集合成的计算复杂性
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
F. Lombardi
中科院分区：
文献类型：
--
作者：
Xiaojun Ma;F. Lombardi
DNA自组装已被提倡作为一种自下而上的制造技术来取代纳米级的光刻技术。然而，为有限大小的任意目标模式设计 DNA 瓦片集（以确保其组装中的周期性重复）的问题尚未在技术文献中得到充分解决。本文考虑了用于 DNA 自组装的瓦片集的合成，并将其作为组合优化问题进行分析，以确定其计算复杂性。这个问题被称为 PATS（模式组装图块集合成）。为 PATS 的 NP 完整性提供了证明。
DNA self-assembly has been advocated as a bottom-up manufacturing technology to supersede photolithography technology at nanometer scale. However, the issue of designing a DNA tile set for an arbitrary target pattern of finite size (as to ensure periodic repetition in its assembly) has not been fully addressed in the technical literature. This paper considers the synthesis of tile sets for DNA self-assembly and analyzes it as a combinatorial optimization problem to establish its computational complexity. This problem is referred to as PATS (pattern assembling tile-set synthesis). A proof is provided for the NP-completeness of PATS.