| 基于DNA折纸术求解图的顶点着色问题的方法 |
| |
| 引用本文： | 麻晶晶, 许进. 基于DNA折纸术求解图的顶点着色问题的方法[J]. 电子与信息学报, 2021, 43(6): 1750-1755. doi: 10.11999/JEIT200203 |
| |
| 作者姓名： | 麻晶晶 许进 |
| |
| 作者单位： | 1.山西财经大学统计学院 太原 030000;;2.北京大学信息科学技术学院 北京 100871 |
| |
| 基金项目： | 国家自然科学基金(61801279) |
| |
| 摘 要： | 
该文基于DNA折纸术,设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法。利用DNA折纸术可以构建出具有特定形状的DNA折纸结构。这些结构可以用来编码图的顶点和边,由于这些结构具有粘性末端,因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构。
利用DNA-纳米颗粒共聚体的属性和电泳等实验方法,可以筛选出正确的符合条件的图的顶点着色方案。该方法是一种高度并行的方法,可以极大地降低求解图的顶点着色问题的复杂度。
|
| 关 键 词： | DNA计算 DNA折纸术 DNA-纳米颗粒共聚体 自组装 顶点着色问题 |
| 收稿时间： | 2020-03-24 |
| 修稿时间： | 2020-08-20 |
|
| 点击此处可从《电子与信息学报》浏览原始摘要信息 |
|
点击此处可从《电子与信息学报》下载免费的PDF全文 |
|
