DNA Computing In Graph Theory

DNA computing is a new method of simulating biology molecular DNA-structure and relying molecular biology technology on computing. It set up the precedent of chemistry as a computing tool, and it has a splendid future.Adleman first published his method of DNA computing on science in 1994, using DNA computing solved the problem of Hamilton path in graph theory, and got success in experiment. The DNA computing is a complete new concept. It has broken through the bondage of traditional structure of computer. The basic theory of DNA computing is: Encode information using the special structure of DNA double helix and nucleotides match rule, and mapping the object to operating to DNA molecules strands, and under the control of enzyme building a data pool, then using the rules appointed mapping the DNA molecules strands to a high speed parallel data computing bio-chemistry procedure. At last, using molecule biology technology such as polymerization chain reaction (PCR), ultrasonic degradation, hybridization, clone, trap, molecules purify, electrophoresis, magnet-bead separate and so on, detect the result of the reaction. So the core matter is leting the encoded DNA strands as input, and in test tube or other carrier take place specific bio-chemistry reactions controlled, then achieve the computing procedure to give the whole result space after the reaction.The efforts in this paper mainly include the following DNA computing model of three contents of the graph theory :The way of DNA computing of the minimal spanning tree :the minimal spanning tree problem is important and has profound implication .The algorithm of solving the minimum spanning tree has lots of methods.The methods of Kruskal escaping circle and destroying circle which are often used to solve the minimum spanning tree must solve circle.This is very tiring.In this paper , according to the basic definition of minimum spanning tree and DNA computing, we give a algorithm of DNA computing by way of molecule biology technology such as electroporesis and probe separate and sequencing.Through this method , we can find a graph of the minimum spanning tree most using n minus one walking.Using the huge parallelism of DNA sticker models , we first decompose the vertex-coloring problems of graph into vertex-independent set problems and vertex-partition problems from the essence of problems and show DNA sticker algorithms of the two problems. Then we solve vertex-coloring probles of graph transferring the two algorithms.No-direction weight Hamilton path problem. Hamilton path is about connected chart, has a path routed every vertex once and only once we call it Hamilton path. If has a Hamilton path that can go back to the vertex begin we call it Hamilton loop, while the contrast we call Hamilton path. If every edge give correspond weight the problem become the Hamilton path with weight. Adleman's experiment research the direction Hamilton path problem with no weight. While we discuss in this paper is about Hamilton path with weight, so we have to treat two things about the weight and the direction. And the main problem is to solve the problem of weight, as to the direction we could give a transform of a no-direction edge to two direction edge. To weight we take use of different GC content to represent different weight, let heavy weight edge with higher GC content or have the lower; As to match of GC it form a three covalent bond has a higher divide-temperature (Tm ) compared with the two covalent bond of AT, so we could detect the path with lower weight easily according to their different divide-temperature. We adopt the method of stick short piece to random produce all path, detect the result we adopt the way of pyrogenation and PCR take place together, first metamorphic unit have lower weight and be amplified first, and this point solve the problem of weight express and separate. This kind of expression of weight has a good elicitation meaning towards such problems.