On the Computational Complexity of Tile Set Synthesis for DNA Self-Assembly

摘要

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.