| DNA computing is the most attracted in the field of biological computing.The field of DNA computing in its present form started with Adleman's celebrated experiment in 1994.This paper discusses the algorithm on DNA computing solving Hamilton path in molecular biology techniques and some coloring problems.Firstly, in which the paper first analyses the sufficient condition of Hamilton and Research on Hamilton. Hamilton Cycle Problem is one of the most ancient projects in the graph theory. Up to now, it is an unsolved and difficult problem in world. Especially, it is a NP-problem to look for the sufficient condition of Hamilton.Then, this paper presents history before appearing, research conditions, base of biology of DNA computing and some base of theory & operations of DNA computing for solution to Hamilton Cycle Problem.DNA computer was born in searching for parallel algorithm. The modern electronic computer based on the Universal Turing Machine is difficult to realize parallel computing. But DNA computing creates a kind of new computing space and gets another different computing method and computing theory completely.The operations of DNA computing are extract, cutting, melting, annealing, synthesis, hybrid, PCR(PolymeraseChainReaction), detest, separate, Gel Electrophoresis, Bead Separation, paste and union.Finally discusses some problems of DNA computing in future research.That advantages & application prospect& technical problems on DNA computer.The advantages on DNA computer are calculating fast and low energy resources and high store consumption and parallel work can be realized realy.The application prospect on DNA computer are: 1. Solving some NP problems 2.Data secret added and solved 3.intellect controled 4. Biochemistry, combination chemistry, medical science 5. Boolean circuit and data flow logical operation.The technical problems on DNA computer are error dispelled problem in DNA computing and operation technique fastly and the structure of DNA computing systems aren't form and the cost of DNA is high etc.Secondly, it puts forward simple models for solving simple problems. Thereby it represents further evidence for the ability of DNA computing to solve the larger hard problems, NP—Complete search problems.and discusses some problems of the false answers and the countermeasure delete operations. It frist puts forward a small graph simple models according to Adleman's celebrated experiment and introducts the thinking and method and the biological laboratory procedure of DNA computing solving Hamilton graph with compact language,then extends the scale to study NP problems (Hamilton graph problems) and discusses the complex of computing for the problem's complex.The procedures of DNA computing'model include problem describing and algorithm designing and DNA computing' realization.This method also suits large graph in principle. This method'crux is the large scale running parallel calculation and Watson-Crick's supplement each other. To solving HPP problems, Adleman's method bases of the following Non-deterministic Algorithm:Import: A direction graph G has n vertexs; we can fix a start vertex vin and an end vertex vout.Step 1: Generate random cycle through the graph.Step 2: Keep only those cycle that begin with vertex vin and end with vertex vout.Step 3: If the graph has vertices. then keep only those cycle that enter exactly vertices.Step 4: Keep only those paths that enter all of the vertices of the graph at least once.Export: If any cycles remain, then G is Hamilton graph; otherwise G isn' t Hamilton graph. Lastly, it discusses the new application of DNA computing for NP problems that is DNA computing of graph vertex coloring problem and DNA algorithm for edge—coloring problem. Using DNA computing to solve the coloring problems that is having the coloring problems decompose to vertex independent sets problems and vertex dividing problems. This algorithm has the vertex (edge) DNA coding decompose to two parts, one stores vertex (edge) and chromatic place's two dimensional data, another stores chromatic numeral value.First of all we transform NP problems to SAT problems in polynomials time, To the beginning tube T0,it chooses the operation of the sticker model and cites Discard show 'give up' operation,and gives solving vertex k-coloring problem's algorithm of graph G based of Lipton's thinking on solving SAT problems. Then adopt wholesale delete operations in the delete operations of DNA computing. Thereby it successfully solved the coloring problem. With society and technology developping, a lot of larger hard systems appear in the field of project. In which is filled of various Non-Linear problems. All kinds of difficult complete problems could be seen everywhere. But DNA computer is hoped to solve the larger hard problems that the modern electronic computer couldn't solve.Using DNA computing to solve the coloring problems has an important practical meaning and a good application prospect in lots of fields. |
