Chinese Journal of Computers   Full Text
Title	A DNA Computing Model for Graph Vertex Coloring Problem
Authors	QIANG Xiao-Li ZHAO Dong-Ming ZHANG Kai
Address	(Key Laboratory of High Confidence Software Technologies of Ministry of Education, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871)
Year	2009
Issue	No.12(2332—2337)
Abstract &   Background	Abstract DNA computing is a novel computation paradigm with DNA molecules as “data”, and biochemistry trials as “information processing instruments”. In this paper, a DNA computing model to solve graph vertex 3-coloring problem is proposed based on enzyme digestion reactions. The graph vertex coloring problem is encoded by double encoding method and the false solutions deletion and the true solutions detection are updated and automized partly after enzyme digestion reactions and polymerase chain reaction. This method could be easier and faster to read out the solution. Especially, the procedure of solution detection is similar to DNA sequencing technology. Keywords DNA computing; graph vertex coloring problem; encoding Background DNA computing is a novel computation paradigm with DNA molecules as “data”, and biochemistry trials as “information processing instruments”. Because of its massive parallelism, high-density storage and energy efficiency, DNA computing attracts the concern of many scientists with different backgrounds. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. The results of these assays indicate that DNA computing is superior to electronic computer in solving some NP-complete problem. However, many issues still exist in DNA computing. It is important and interesting for further study on DNA computing. In this paper, a DNA computing model to solve graph vertex 3-coloring problem was proposed based on enzyme digestion reactions. The graph vertex coloring problem is encoded by double encoding method, and the false solutions deletion and the true solutions detection are updated and automized partly after enzyme digestion reactions and polymerase chain reaction. By using this model the proper color of any graph will be obtained after times of digestion reaction and times of PCR operation, where is the number of edges in a graph, and is the chromatic number of a graph. Compared with other DNA computing algorithms, this method could be easier and faster to read out the solution. Especially, the procedure of solution detection similar to DNA sequencing technology.