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

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

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

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.