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

• 作者: 俞洋 晁洁 苏邵
• 来源期刊: 中国科学（化学）
• 关键词: 哈密顿路径 DNA折纸术 磁珠筛选 原子力显微镜
• 年，卷（期）: 2015,（11）
• 所属期刊栏目: 论文
• 页码范围: 1226-1230
• 页数: 5页
• 语种: 中文
• DOI: 10.1360/N032015-00035

摘要

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