|
DNA computing is a field of molecular biology and computer science cross each other, merging the new cross-over study. DNA computing is the use of a large number of different DNA hybridization generated similar to a mathematical process according to the qualification of its screening in a controlled biochemical reactions. 1994 Dr. Adleman successful use of DNA computing to solve the seven vertex weighted graph Hamiltonian path problem, which proves that DNA computing is feasible, not just theoretical ideas. With the development of computer science and mathematics, graph theory has been applied to various fields, including physics, chemistry, communication sciences, computer technology, civil engineering, architecture, operations research, bio-genetics, psychology, sociology, economic science, anthropology and linguistics, graph theory provides a mathematical model for a binary relation system; FIG. intuitive, beautiful performance characteristics can make a clear understanding of the reality of the system. Many of the problems in the real world mathematical abstract form can be described with a picture. Such as the Internet, transportation networks, communications networks, integrated circuits, molecular structure and so can be used diagrams to describe. Graph theory has become the people to study science and social science is an important tool, its application has become increasingly important. Solve some of the problems of the graph theory, there are still some difficulties, such as: the Hamiltonian path problem, shortest path problems. DNA computation compared with conventional calculation method having a high degree of parallelism, the speed, the advantages of large information storage capacity. This is to solve some of the problems in graph theory the full NP problem in graph theory, in particular, to provide a new way, and has great practical significance. In this paper, several classical problems in graph theory given their DNA algorithm. Firstly, the DNA algorithm to solve the minimum spanning tree problem. CG content to encode weights, and put forward the best value range of the CG concentration. Second, given the DNA algorithm to solve the undirected weighted graph Hamiltonian path problem. Here is different from the the Adleman models Encoding solve the problem. And then gives the the DNA algorithm paste system and delete system solutions to a weighted graph shortest path problem. Finally, the use of multi-stage separation technology improved DNA to solve the problem of vertex coloring paste algorithm. And use of computer simulation in Java Swing and multi-threading technology on the minimum spanning tree problem.
|