A “DNA origami”based approach to the solution of graph coloring problem
Yu Yang1，Su Shao2，Chao Jie2*
Author information+
{{custom_zuoZheDiZhi}}
About authors:
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
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.
Yu Yang1，Su Shao2，Chao Jie2*.
A “DNA origami”based approach to the solution of graph coloring problem[J]. Journal of Nanjing University(Natural Sciences), 2016, 52(4): 656
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[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.
PDF(1881345 KB)
