|本期目录/Table of Contents|

[1]俞 洋,苏 邵,晁 洁*.基于“DNA折纸术”设计图着色问题的解决方案[J].南京大学学报(自然科学),2016,52(4):656.[doi:10.13232/j.cnki.jnju.2016.04.010]
 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.[doi:10.13232/j.cnki.jnju.2016.04.010]





A “DNA origami”­based approach to the solution of graph coloring problem
俞 洋1苏 邵2晁 洁2*
Yu Yang1Su Shao2Chao Jie2*
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
DNA computingDNA origamiNP­complete problemgraph coloring problemgold nanoparticle
色数是图论中的一个重要的参数,其属于著名NP(Non­deterministic Polynomial)-完全问题范畴.巨量的着色方案使验证变得相当困难,以至于在传统计算机上无法实现.目前已经有多种算法用于研究图定点着色问题,比如遗传算法,粒子群算法,神经网络算法和模拟退火算法等.随着DNA自组装技术与DNA计算机研究的展开,一些NP-完全问题以及NP-难问题的计算模型被相继提出.除了传统的DNA分子结构被用作计算材料外,其他的DNA分子结构也被用于分子生物计算,比如质粒DNA分子、分子信标结构以及DNA Tile等.采用DNA纳米折纸结构编码信息,借助于纳米结构之间的粘性末端进行自组装,给出了一种非确定性的图着色模型.通过创建数以亿计的参与计算的DNA纳米折纸结构,该算法可以并行的测试每种可能的着色方案.
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 Non­deterministic)­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 proof­of­concept use of DNA as a form of computation to solve the seven­point Hamiltonian path problem.DNA computing dedicates to use DNA,biochemistry together with molecular biology hardware to take the place of the traditional silicon­based computer technologies.Theory,experiments and applications are the concerns in the DNA computing research field.Some NP­complete problems and the computational model of NP­complete problems have been put forward.Typically,DNA strands with special enzymes are used as the calculating materials.With the development of DNA self­assembly 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 origami­based nanostructures are employed for encoding information.Through the self­assembly of the sticky ends in the DNA origami­based 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 origami­based nanostructures are designed large enough which could be readily detected by atomic force microscopy and transmission electron microscopy.


[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 logic­gated 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 u­formulas 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 self­assembly of DNA.Ph.D Dissertation.California Institute of Technology,1998.
[9]  Mao C,LaBean T,Reif J,et al.Logical computation using algorithmic self­assembly of DNA trip1e crossover molecules.Nature,2000,407:493-496.
[10]  Adleman L,Cheng Q,Goel A,et al.Combinatorial optimization problems in self­assembly.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 constant­size tileset.Journal of Algorithms,2008,63(4):151-166.
[13]  Jonoska N,Seeman N.Computing by molecular self­assembly.Interface Focus,2012,2:504-511.
[14]  Di Blas A,Jagota A,Hughey R.Energy function­based 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:Addison­Wesley 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.Three­dimensional DNA structures in computing.Biosystems,1999,52:143-153.
[21]  Wu G,Jonoska N,Seeman N.Construction of a DNA nano­object 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 three­dimensional 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.






* 通讯联系人, E ­ mail iamjchao@njupt.edu.cn
更新日期/Last Update: 2016-07-24