基于“DNA折纸术”设计图着色问题的解决方案

• 作者: 俞洋 晁洁 苏邵
• 来源期刊: 南京大学学报（自然科学版）
• 学科: 工学
• 关键词: DNA计算 DNA“折纸术” NP-完全问题 图着色问题 纳米金颗粒
• 年，卷（期）: 2016,（4）
• 页码范围: 656-661
• 页数: 6页
• 分类号: TP301
• 字数: 2469字
• 语种: 中文
• DOI: 10.13232/j.cnki.jnju.2016.04.010

摘要

色数是图论中的一个重要的参数，其属于著名 NP(Non-deterministic Polynomial)-完全问题范畴。巨量的着色方案使验证变得相当困难，以至于在传统计算机上无法实现。目前已经有多种算法用于研究图定点着色问题，比如遗传算法，粒子群算法，神经网络算法和模拟退火算法等。随着 DNA 自组装技术与 DNA 计算机研究的展开，一些NP-完全问题以及NP-难问题的计算模型被相继提出。除了传统的DNA分子结构被用作计算材料外，其他的DNA分子结构也被用于分子生物计算，比如质粒 DNA分子、分子信标结构以及 DNA Tile 等。采用 DNA 纳米折纸结构编码信息，借助于纳米结构之间的粘性末端进行自组装，给出了一种非确定性的图着色模型。通过创建数以亿计的参与计算的DNA纳米折纸结构，该算法可以并行的测试每种可能的着色方案。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	俞洋	上海科技管理干部学院电子信息系	6	31	4.0	5.0