许进2
1.山西财经大学统计学院 太原 030000
2.北京大学信息科学技术学院 北京 100871
基金项目:国家自然科学基金(61801279)
详细信息
作者简介:麻晶晶：女，1983年生，讲师，从事生物计算等研究
许进：男，1959年生，教授，从事生物计算等研究
通讯作者:麻晶晶 casy@pku.edu.cn
中图分类号:O157.6计量
文章访问数:557
HTML全文浏览量:192
PDF下载量:38
被引次数:0
出版历程
收稿日期:2020-03-24
修回日期:2020-08-20
网络出版日期:2020-08-27
刊出日期:2021-06-18
A Method for the Graph Vertex Coloring Problem Based on DNA Origami
Jingjing MA1,,,Jin XU2
1. School of Statistics, Shanxi University of Finance and Economy, Taiyuan 030000, China
2. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Funds:The National Natural Science Foundation of China (61801279)
摘要
摘要:该文基于DNA折纸术，设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法。利用DNA折纸术可以构建出具有特定形状的DNA折纸结构。这些结构可以用来编码图的顶点和边，由于这些结构具有粘性末端，因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构。利用DNA-纳米颗粒共聚体的属性和电泳等实验方法，可以筛选出正确的符合条件的图的顶点着色方案。该方法是一种高度并行的方法，可以极大地降低求解图的顶点着色问题的复杂度。
关键词:DNA计算/
DNA折纸术/
DNA-纳米颗粒共聚体/
自组装/
顶点着色问题
Abstract:Based on the DNA origami technique, a method for the graph vertex coloring problem is proposed via the self-assembly of DNA origami structures. Utilizing the DNA origami technique different DNA origami structures with specific shapes are constructed. These structures are utilized to encode the information of a graph’s vertices and edges, and because these structures have sticky ends, so they can assemble to advanced structures which stands for different answers of the graph vertex coloring problem via specific molecular hybridization. Utilizing the property of DNA nanoparticle conjugation and electrophoresis as well as other experimental methods, the correct answer of the graph vertex coloring problem can be detected. This method is highly parallel, and can greatly reduce the complexity of the graph vertex coloring problem.
Key words:DNA computing/
DNA origami/
DNA-nanoparticle conjugation/
Self-assembly/
Graph vertex coloring problem
PDF全文下载地址:
https://jeit.ac.cn/article/exportPdf?id=a409a9e7-763c-4b88-b850-7f6c9b7bd60f
