基于“DNA折纸术”设计图着色问题的解决方案

南京大学学报(自然科学版) ›› 2016, Vol. 52 ›› Issue (4): 656–.

基于“DNA折纸术”设计图着色问题的解决方案

俞　洋¹，苏　邵²，晁　洁^2*

出版日期:2016-07-24 发布日期:2016-07-24
作者简介: 1.上海科技管理干部学院电子信息系，上海，201800；2.南京邮电大学材料科学与工程学院，有机电子与信息显示国家重点实验室培育基地&信息科学与纳米技术研究院，先进生物与
化学制造协同创新中心(国家级2011协同创新中心)，南京，210023
基金资助:

基金项目：江苏省科技厅面上项目(BK20151504)，南京邮电大学人才引进项目(NY214175)

收稿日期：2016－04－14
* 通讯联系人， E mail ： iamjchao@njupt.edu.cn

A “DNA origami”based approach to the solution of graph coloring problem

Yu Yang¹，Su Shao²，Chao Jie²*

Online:2016-07-24 Published:2016-07-24
About author: 1.Information Technology Department，Shanghai Institute of Science & Technology Management，Shanghai，201800，China；2．Key Laboratory for Organic Electronics and Information Displays & Institute of Advanced Materials(IAM)，
Jiangsu National Synergetic Innovation Center for Advanced Materials(SICAM)，Nanjing，210023，China

摘要/Abstract

摘要： 色数是图论中的一个重要的参数，其属于著名NP(Nondeterministic Polynomial)－完全问题范畴．巨量的着色方案使验证变得相当困难，以至于在传统计算机上无法实现．目前已经有多种算法用于研究图定点着色问题，比如遗传算法，粒子群算法，神经网络算法和模拟退火算法等．随着DNA自组装技术与DNA计算机研究的展开，一些NP－完全问题以及NP－难问题的计算模型被相继提出．除了传统的DNA分子结构被用作计算材料外，其他的DNA分子结构也被用于分子生物计算，比如质粒DNA分子、分子信标结构以及DNA Tile等．采用DNA纳米折纸结构编码信息，借助于纳米结构之间的粘性末端进行自组装，给出了一种非确定性的图着色模型．通过创建数以亿计的参与计算的DNA纳米折纸结构，该算法可以并行的测试每种可能的着色方案．

Abstract: In the graph theory，graph coloring is an assignment of labels which are traditionally called ”colors” to elements of a graph that subject to certain constraints.Graph coloring belongs to the famous category of NP(Polynomial Nondeterministic)complete problems.The huge coloring schemes make the verification too difficult to be achieved in traditional computers.Until now，there are many algorithms used in the study of graph coloring problem，such as genetic algorithm，particle swarm optimization algorithm，neural network algorithm and simulated annealing algorithm.DNA computing is a branch of computing which can be traced back to 1994 when Aldeman firstly demonstrated a proofofconcept use of DNA as a form of computation to solve the sevenpoint Hamiltonian path problem.DNA computing dedicates to use DNA，biochemistry together with molecular biology hardware to take the place of the traditional siliconbased computer technologies.Theory，experiments and applications are the concerns in the DNA computing research field.Some NPcomplete problems and the computational model of NPcomplete problems have been put forward.Typically，DNA strands with special enzymes are used as the calculating materials.With the development of DNA selfassembly technology，other DNA nanostructures are also used for molecular biology，such as plasmid DNA molecules，molecular beacon structures，as well as DNA Tiles.In this paper，the DNA origamibased nanostructures are employed for encoding information.Through the selfassembly of the sticky ends in the DNA origamibased nanostructures and the special enzymes which can identify the restriction sites，we demonstrated a deterministic graph coloring model.Based on the creation of millions of DNA origami nanostructures involved in the calculation，this algorithm can be parallelized in testing each possible coloring scheme.To easily address the graph coloring problem，the DNA origamibased nanostructures are designed large enough which could be readily detected by atomic force microscopy and transmission electron microscopy.

俞　洋¹，苏　邵²，晁　洁^2*. 基于“DNA折纸术”设计图着色问题的解决方案[J]. 南京大学学报(自然科学版), 2016, 52(4): 656–.

Yu Yang¹，Su Shao²，Chao Jie²*. A “DNA origami”based approach to the solution of graph coloring problem[J]. Journal of Nanjing University(Natural Sciences), 2016, 52(4): 656–.

参考文献

[1]　Feynman R．There’s plenty of room at the bottom.Caltech Engineering and Science，1960，23(5)：22－36.
[2] Adleman L．Molecular computation of solution to combinatorial problems.Science，1994，66(11)：1021－1024.
[3] Douglas S，Bachelet I，Church G．A logicgated nanorobot for targeted transport of molecular payloads.Science，2012，335：831－834.
[4] Garro B，Rodríguez K，Vázquez R．Classification of DNA microarrays using artificial neural networks and ABC algorithm.Applied Soft Computing，2015，38：548－560.
[5] Dannenberg F，Kwiatkowska M，Thachuk C，et al.DNA walker circuits：Computational potential，design，and verification.Natural Computing，2015，14(2)：195－211.
[6] Hagiya M，Arita M，Kiga D，et al.Towards parallel evolution and learning of boolean uformulas with molecules.In：Proceedings of the 3rd DIMACS Workshop on DNA Based Computers.University of Pefmsylvania，Baltimore，1997，105－114.
[7] Sakamoto K，Kiga D，Komiya K，et al.State Transitions by molecules.Biosystems，1999，52：81－91.
[8] Winfree E．Algorithmic selfassembly of DNA.Ph.D Dissertation.California Institute of Technology，1998.
[9] Mao C，LaBean T，Reif J，et al.Logical computation using algorithmic selfassembly of DNA trip1e crossover molecules.Nature，2000，407：493－496.
[10] Adleman L，Cheng Q，Goel A，et al.Combinatorial optimization problems in selfassembly.In：The 34th Annual ACM Symposium on Theory of Computing.Montreal，Quebec，Canada，2002，19－21.
[11] Brun Y．Arithmetic computation in the tile assembly model：Addition and multiplication.Theoretical Computer Science，2006，378：17－31.
[12] Brun Y．Solving satisfiability in the tile assembly model with a constantsize tileset.Journal of Algorithms，2008，63(4)：151－166.
[13] Jonoska N，Seeman N．Computing by molecular selfassembly.Interface Focus，2012，2：504－511.
[14] Di Blas A，Jagota A，Hughey R．Energy functionbased approaches to graph coloring.IEEE Transactions on Neural Networks，2002，13(1)：81－90.
[15] Goldberg D．Genetic algorithm in search，optimization and machine learning.Boston：AddisonWesley Publishing，1989，208－211.
[16] Halldorsson M．A still better performance guarantee for approximate graph coloring.Information Processing Letters，1994，45：19－23.
[17] 徐　杰，杜　文，李宗平．基于模拟退火算法和图着色的调车机车安排研究．铁道学报，2003，25(3)：24－30.(Xu J，Du W，Li Z P，et al.Study on the plan of using shunting locomotives based on stimulated annealing algorithm and graph coloring.Journal of the China Railway Society，2003，25(3)：24－30.)
[18] 马季兰，杨玉星．基于粘贴模型的图顶点着色问题的DNA算法．计算机应用，2006，26(12)：2998－3000.(Ma J L，Yang，Y X．DNA algorithm of graph vertex coloring problem based on sticker model.Computer Applications，2006，26(12)：2998－3000.)
[19] 强小利，赵东明，张　凯．图顶点着色问题的DNA计算模型．计算机学报，2009，32(12)：2332－2337.(Qiang X，Zhao D M，Zhang K．A DNA computing model for graph vertex coloring problem.Chinese Journal of Computers，2009，32(12)：2332－2337.)
[20] Jonoska N，Karl S，Saito M．Threedimensional DNA structures in computing.Biosystems，1999，52：143－153.
[21] Wu G，Jonoska N，Seeman N．Construction of a DNA nanoobject directly demonstrates computation.Biosystems，2009，98：80－84.
[22] Rothemund P．Folding DNA to create nanoscale shapes and patterns，Nature 2006，440：297－302.
[23] Dietz H，Douglas S，Shih W．Folding DNA into twisted and curved nanoscale shapes.Science，2009，325：725－730.
[24] Han D，Pal S，Nangreave J，et al.DNA origami with complex curvatures in threedimensional space.Science，2011，332：342－346.
[25] Dunn K，Dannenberg F，Ouldridge T，et al.Guiding the folding pathway of DNA origami.Nature，2015，525(7567)：82－86.
[26] Funke J，Dietz.Placing molecules with Bohr radius resolution using DNA origami.Nature Nanotechnology，2016，11：47－52.
[27] Jones M，Seeman N，Mirkin C．Programmable materials and the nature of the DNA bond.Science，2015，347(6224)：1－23.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed