基于DNA折纸术求解图的顶点着色问题的方法

• 作者: 麻晶晶 许进
• 来源期刊: 电子与信息学报
• 关键词: DNA计算 DNA折纸术 DNA-纳米颗粒共聚体 自组装 顶点着色问题
• 年，卷（期）: 2021,（6）
• 所属期刊栏目: 图论与系统优化|Graph Theory and System Optimization
• 页码范围: 1750-1755
• 页数: 6页
• 分类号: O157.6
• 语种: 中文
• DOI: 10.11999/JEIT200203

摘要

该文基于DNA折纸术,设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法.利用DNA折纸术可以构建出具有特定形状的DNA折纸结构.这些结构可以用来编码图的顶点和边,由于这些结构具有粘性末端,因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构.利用DNA-纳米颗粒共聚体的属性和电泳等实验方法,可以筛选出正确的符合条件的图的顶点着色方案.该方法是一种高度并行的方法,可以极大地降低求解图的顶点着色问题的复杂度.