2018, Volume 4, Issue 1
Engineering >> 2018, Volume 4, Issue 1 doi: 10.1016/j.eng.2018.02.011
A DNA Computing Model for the Graph Vertex Coloring Problem Based on a Probe Graph
a Key Laboratory of High Confidence Software Technologies of Ministry of Education, Institute of Software, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
b Institute of Novel Computer Science and Intelligent Software, Guangzhou University, Guangzhou 510006, China
c School of Computer Science, Wuhan University of Science and Technology, Wuhan 430081, China
d School of Control and Computer Engineering, North China Electric Power University, Beijing 102206, China
Next Previous
Abstract
The biggest bottleneck in DNA computing is exponential explosion, in which the DNA molecules used as data in information processing grow exponentially with an increase of problem size. To overcome this bottleneck and improve the processing speed, we propose a DNA computing model to solve the graph vertex coloring problem. The main points of the model are as follows:①The exponential explosion problem is solved by dividing subgraphs, reducing the vertex colors without losing the solutions, and ordering the vertices in subgraphs; and②the bio-operation times are reduced considerably by a designed parallel polymerase chain reaction (PCR) technology that dramatically improves the processing speed. In this article, a 3-colorable graph with 61 vertices is used to illustrate the capability of the DNA computing model. The experiment showed that not only are all the solutions of the graph found, but also more than 99% of false solutions are deleted when the initial solution space is constructed. The powerful computational capability of the model was based on specific reactions among the large number of nanoscale oligonucleotide strands. All these tiny strands are operated by DNA self-assembly and parallel PCR. After thousands of accurate PCR operations, the solutions were found by recognizing, splicing, and assembling. We also prove that the searching capability of this model is up to O(359). By means of an exhaustive search, it would take more than 896 000 years for an electronic computer (5 1014 s1) to achieve this enormous task. This searching capability is the largest among both the electronic and non-electronic computers that have been developed since the DNA computing model was proposed by Adleman’s research group in 2002 (with a searching capability of O(220)).
Figures
Fig.1
Fig.2
Fig.3
Fig.4
Fig.5
Fig.6
Fig.7
Fig.8
Fig.9
Fig.10
Fig.11
Fig.12
Fig.13
Fig.14
Fig.15
Fig.16
References
[ 1 ] Feynman RP. Minaturization. New York: Reinhold; 1961.
[ 2 ] Adleman LM. Molecular computation of solutions to combinatorial problems. Science 1994;266(5187):1021–4. link1
[ 3 ] Lipton RJ. DNA solution of hard computational problems. Science 1995;268 (5210):542–5. link1
[ 4 ] Ouyang Q, Kaplan PD, Liu S, Libchaber A. DNA solution of the maximal clique problem. Science 1997;278(5337):446–9. link1
[ 5 ] Sakamoto K, Gouzu H, Komiya K, Kiga D, Yokoyama S, Yokomori T, et al. Molecular computation by DNA hairpin formation. Science 2000;288 (5469):1223–6. link1
[ 6 ] Rothemund PWK. A DNA and restriction enzyme implementation of turing machines. In: Lipton RJ, Baum EB, editors. DNA based computers. Providence: American Mathematical Society; 1995. p. 75–119.
[ 7 ] Benenson Y, Paz-Elizur T, Adar R, Keinan E, Livneh Z, Shapiro E. Programmable and autonomous computing machine made of biomolecules. Nature 2001;414 (6862):430–4. link1
[ 8 ] Benenson Y, Gil B, Ben-Dor U, Adar R, Shapiro E. An autonomous molecular computer for logical control of gene expression. Nature 2004;429 (6990):423–9. link1
[ 9 ] Winfree E. Algorithmic self-assembly of DNA [dissertation]. Pasadena: California Institute of Technology; 1998. link1
[10] Braich RS, Chelyapov N, Johnson C, Rothemund PW, Adleman L. Solution of a 20-variable 3-SAT problem on a DNA computer. Science 2002;296 (5567):499–502. link1
[11] Berge C, Minieka E. Graphs and hypergraphs. New York: Elsevier Science Publishing Co, Inc.; 1973.
[12] Briggs P, Cooper KD, Dennedy K, Torczon L. Coloring heuristics for register allocation. In: Proceedings of the ACM SIGPLAN 1989 conference on programming language design and implementation. 1989 Jun 19–23; Portland, OR, USA; 1989. p. 275–84. link1
[13] Chaitin GJ. Register allocation & spilling via graph coloring. In: Proceedings of the ACM SIGPLAN 1982 conference on compiler construction; 1982 Jun 23–25; Boston, MA, USA; 1982. p. 98–105. link1
[14] Johnson DS. Worst case behavior of graph coloring algorithm. In: Proceedings of the 5th southeastern conference on combinatorics, graph theory and computing; 1974 Feb 25–Mar 1; Boca Raton, FL, USA; 1974. p. 513–27.
[15] Blum A. New approximation algorithms for graph coloring. J Assoc Comput Mach 1994;41(3):470–516. link1
[16] Karger D, Motwani R, Sudan M. Approximate graph coloring by semi-definite programming. J Assoc Comput Mach 1998;45(2):246–65. link1
[17] Schiermeyer I. Deciding 3-colorability in less than O(1.415n) steps. In: Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science; 1993 Jun 16–18; Utrecht, The Netherlands. London: Springer; 1993. p. 177–88. link1
[18] Beigel R, Eppstein D. 3-coloring in time O(1.3289n). J Algorithms 2005;54 (2):168–204. link1
[19] Jonoska N, Karl SA, Saito M. Three dimensional DNA structures in computing. Biosystems 1999;52(1–3):143–53. link1
[20] Jonoska N, Sa-Ardyen P, Seeman NC. Computation by self-assembly of DNA graphs. Genet Program Evolvable Mach 2003;4(2):123–37. link1
[21] Sa-Ardyen P, Jonoska N, Seeman NC. Self-assembling DNA graphs. Nat Comput 2003;2(4):427–38.
[22] Liu W, Zhang F, Xu J. A DNA algorithm for the graph coloring problem. J Chem Inf Comput Sci 2002;42(5):1176–8. link1
[23] Gao L, Xu J. A DNA algorithm for graph vertex coloring problem. Acta Electronic Sinica 2003;31:494–6.
[24] Xu J, Qiang X, Fang G, Zhou K. A DNA computer model for solving vertex coloring problem. Chin Sci Bull 2006;51(20):2541–9. link1
[25] Garey MR, Johnson DS. Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman & Co.; 1979. link1
[26] Bondy JA, Murty USR. Graph theory with applications. New York: American Elsevier Publishing Company, Inc.; 1976.
[27] Zhang K, Pan L, Xu J. A global heuristically search algorithm for DNA encoding. Prog Nat Sci 2007;17(6):745–9. link1
[28] Biggs N. Algebraic graph theory. 2nd ed. Cambridge: Cambridge University Press; 1993.
京公网安备 11010502051620号
