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

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