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

A Method for the Graph Vertex Coloring Problem Based on DNA Origami

作　　者：麻晶晶 许进[2] MA Jingjing;XU Jin(School of Statistics,Shanxi University of Finance and Economy,Taiyuan 030000,China;School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China)

机构地区：[1]山西财经大学统计学院,太原030000 [2]北京大学信息科学技术学院,北京100871

出　　处：《电子与信息学报》2021年第6期1750-1755,共6页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(61801279)。

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

关 键 词：DNA计算 DNA折纸术 DNA-纳米颗粒共聚体 自组装 顶点着色问题 

分 类 号：O157.6[理学—数学]