Please wait a minute...
Submit  |   Chinese  | 
 
Advanced Search
   Home  |  Online Now  |  Current Issue  |  Focus  |  Archive  |  For Authors  |  Journal Information   Open Access  
Submit  |   Chinese  | 
Engineering    2018, Vol. 4 Issue (1) : 61 -77     https://doi.org/10.1016/j.eng.2018.02.011
Research |
A DNA Computing Model for the Graph Vertex Coloring Problem Based on a Probe Graph
Jin Xu1(),Xiaoli Qiang2,Kai Zhang3,Cheng Zhang1,Jing Yang4
1. 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
2. Institute of Novel Computer Science and Intelligent Software, Guangzhou University, Guangzhou 510006, China
3. School of Computer Science, Wuhan University of Science and Technology, Wuhan 430081, China
4. School of Control and Computer Engineering, North China Electric Power University, Beijing 102206, China
Abstract
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)).

Keywords DNA computing      Graph vertex coloring problem      Polymerase chain reaction     
Fund: 
Corresponding Authors: Jin Xu   
Just Accepted Date: 05 March 2018   Issue Date: 10 April 2018
Service
E-mail this article
E-mail Alert
RSS
Articles by authors
Jin Xu
Xiaoli Qiang
Kai Zhang
Cheng Zhang
Jing Yang
Cite this article:   
Jin Xu,Xiaoli Qiang,Kai Zhang, et al. A DNA Computing Model for the Graph Vertex Coloring Problem Based on a Probe Graph[J]. Engineering, 2018, 4(1): 61 -77 .
URL:  
http://engineering.org.cn/EN/10.1016/j.eng.2018.02.011     OR     http://engineering.org.cn/EN/Y2018/V4/I1/61
References
Related
[1] Zhuo Cheng, Lang Qin, Jonathan A. Fan, Liang-Shih Fan. New Insight into the Development of Oxygen Carrier Materials for Chemical Looping Systems[J]. Engineering, 2018, 4(3): 343 -351 .
[2] Jennifer A. Clark, Erik E. Santiso. Carbon Sequestration through CO2 Foam-Enhanced Oil Recovery: A Green Chemistry Perspective[J]. Engineering, 2018, 4(3): 336 -342 .
[3] Andrea Di Maria, Karel Van Acker. Turning Industrial Residues into Resources: An Environmental Impact Assessment of Goethite Valorization[J]. Engineering, 2018, 4(3): 421 -429 .
[4] Lance A. Davis. Falcon Heavy[J]. Engineering, 2018, 4(3): 300 .
[5] Augusta Maria Paci. A Research and Innovation Policy for Sustainable S&T: A Comment on the Essay ‘‘Exploring the Logic and Landscape of the Knowledge System”[J]. Engineering, 2018, 4(3): 306 -308 .
[6] Ning Duan. When Will Speed of Progress in Green Science and Technology Exceed that of Resource Exploitation and Pollutant Generation?[J]. Engineering, 2018, 4(3): 299 .
[7] Jian-guo Li, Kai Zhan. Intelligent Mining Technology for an Underground Metal Mine Based on Unmanned Equipment[J]. Engineering, 2018, 4(3): 381 -391 .
[8] Veena Sahajwalla. Green Processes: Transforming Waste into Valuable Resources[J]. Engineering, 2018, 4(3): 309 -310 .
[9] Junye Wang, Hualin Wang, Yi Fan. Techno-Economic Challenges of Fuel Cell Commercialization[J]. Engineering, 2018, 4(3): 352 -360 .
[10] Raymond RedCorn, Samira Fatemi, Abigail S. Engelberth. Comparing End-Use Potential for Industrial Food-Waste Sources[J]. Engineering, 2018, 4(3): 371 -380 .
[11] Ning Duan, Linhua Jiang, Fuyuan Xu, Ge Zhang. A Non-Contact Original-State Online Real-Time Monitoring Method for Complex Liquids in Industrial Processes[J]. Engineering, 2018, 4(3): 392 -397 .
[12] Keith E. Gubbins, Kai Gu, Liangliang Huang, Yun Long, J. Matthew Mansell, Erik E. Santiso, Kaihang Shi, Małgorzata Ś liwińska-Bartkowiak, Deepti Srivastava. Surface-Driven High-Pressure Processing[J]. Engineering, 2018, 4(3): 311 -320 .
[13] Steff Van Loy, Koen Binnemans, Tom Van Gerven. Mechanochemical-Assisted Leaching of Lamp Phosphors: A Green Engineering Approach for Rare-Earth Recovery[J]. Engineering, 2018, 4(3): 398 -405 .
[14] Robert S. Weber, Johnathan E. Holladay. Modularized Production of Value-Added Products and Fuels from Distributed Waste Carbon-Rich Feedstocks[J]. Engineering, 2018, 4(3): 330 -335 .
[15] Hualin Wang, Pengbo Fu, Jianping Li, Yuan Huang, Ying Zhao, Lai Jiang, Xiangchen Fang, Tao Yang, Zhaohui Huang, Cheng Huang. Separation-and-Recovery Technology for Organic Waste Liquid with a High Concentration of Inorganic Particles[J]. Engineering, 2018, 4(3): 406 -415 .
Copyright © 2015 Higher Education Press & Engineering Sciences Press, All Rights Reserved.
京ICP备11030251号-2

 Engineering