DNA Computing In Graph Theory

DNA computing is a new field of interdisciplinary research and it generated by computer science and molecular biology which combined with each other. DNA computing is a controlled biochemical reaction which uses a number of DNA hybridization to produce a similar mathematical process and filter it according by some qualification. In 1994, Dr. Adleman successfully solved the Hamiltonion path problem of the Seven vertices by DNA computing, which shows that DNA computing is entirely feasible, and not just a theoretical idea.With the development of computer science and mathematics, graph theory has been applied to various fields, including physics, chemistry, communications science, computer technology, civil engineering, architecture, operations research, bio-genetics, psychology, sociology, Economics, anthropology and linguistics, etc. Graph theory provides a mathematical model for a system that contains binary relation. Using the intuitive, nice features of the graph, people have a clear understanding to system. Many problems in the form of mathematical abstraction can be used to describe by graph, such as the Internet, transportation networks, communications networks, integrated circuits, molecular structure. Graph theory has become an important tool which studys the natural sciences and the social sciences and its application has become increasingly important. But there are still some problems in graph theory, such as the Hamiltonian path problem, the shortest path problems.DNA computation compared with the traditional computing formula has many advantages for example high degree of parallelism, fast computing speed, large capacity of information storage and so on. It provides a new way for solving some graph theory problems, especially NP complete problem. This article studys some classical problems in graph theory and gives their DNA algorithm. First, this article gives the DNA algorithm of figure minimum spanning tree.Here using the different of the CG content to be encoded on the weight, and give the best region of the CG content.Second, this article gives the DNA algorithm of the Hamiltonian path problem, and this algorithm is different from Adleman model. Third, this article solves the shortest path problems by sticker system and Delete system. The last, this article improves the graph vertex coloring problem algorithm. And By Swing and multithreading technology, we simulate the figure minimum spanning tree problem in computer.