基于“DNA折纸术”设计哈密顿路径问题的解决方案

A “DNA origami”-based approach to the solution of Hamilton path problem

哈密顿路径问题是著名的NP-完全问题.本文基于"DNA折纸术"提出了一个通过DNA纳米结构的自组装找出最短哈密顿路径的解决方案.利用"DNA折纸术"可以折叠出具有固定大小的长方形DNA纳米结构,这些结构可用来编码哈密顿路径图中的顶点和路径.这些折纸结构具有黏性末端,可以在溶液中通过分子自组装直接连接起来,从而产生有向无权的不同大小的纳米结构.利用磁珠筛选和电泳等分子生物学手段,可以找到对应于只经过图的顶点一次的最短有向哈密顿路径.该解决方案具有高度并行性,是一种很有潜力的哈密顿路径问题解决方案.

Hamiltonian path problem（HPP） is known to be in the problem class NP-complete. In this paper, a DNA origami-based method for solving the HPP was described. Among the various predefined 2D nanostructures created by DNA origami technology, a square shaped DNA origami body with decoration of numbers was selected for coding the vertexes while their single-stranded arms coded the paths. Because these arms could hybridize with their corresponding ones in the solution, all the paths with possibility would exist after annealing. Take advantage of magnetic beads and gel electrophoresis, the shortest path that pass each vertex once for HPP could easily found under the atomic force microscope. This method not only simplified the experimental procedures for solving the HPP but obtained a direct and readable result, which could also be applied to other problems requiring a massive parallelism in computation.