Research On DNA Algorithms Of Several Problems

With the rapid development of biological techniques, a new discipline—DNA computinghas come into being. DNA computing is a new computing paradigm. It computes with DNA strands as materials, and biochemistry experiments as tools. The massive parallelism, high-density storage and energy efficiency of DNA computing may offset the disadvantages of electronic computers.DNA Researches on DNA computing had been spread out, since 1994, professor Adleman in South California University solved Directed Hamilton Path problem of graph with seven vertexes by biochemistry experiments. The researchers had made big progress, but There are still no DNA algorithms of several classical problems on graph and mathematics. DNA algorithms of some problems had been existed, but still to be improved.The sticker system is a language generative mechanism based on sticking operations and a DNA computation abstract model that follows Watson-Crick complementarity relation to anneal. use of fixed-length DNA strands, free of enzymes and strands expanding, repeated use of materials caused researches on sticker model making a rapid development, and DNA algorithms of many problems were proposed, too. But operation steps were excessive, and precious time was exhausted since only four basic operations of sticker model were adopted in experiments. Multi-separation as well as many basic operations in DNA computing could be carried out in this equipment. So, the operations steps were reduced, and the efficiency in solving problems was improved. The paper introduce the DNA computing algorithm on the the surfaced-based model and the X of the Special tiger planning is from -2 to +2 and a DNA algorithm is shown In the paper. The operating steps are given through an instance. By utilizing the techniques of fluorescence distinguishing, the new algorithm can eliminate all of those false solutions through observing the fluorescence on the surface of DNA molecules and the new proposed algorithm has such good characteristics as simple encoding and low fault rate etc.The following two problems were solved with multi-separation techniques in this thesis.(1) 0-1 integer planning problem. A DNA algorithm based on solution was proposed to solve the 0-1 integer planning prolem problem. the new algorithm can overcome the shortcoming of encoding and the fluorescence. In the paper Multi-separation is used. So, the operations steps were reduced, and the efficiency in solving problems was improved.(2) Knapsack problem. The knapsack was solved in the way of transforming it into the. 0-1 integer planning problem. In the paper Multi-separation is used. So, the operations steps were reduced, and the efficiency in solving problems was improved.The specific instances were given to solve the two problems above. And the solutions were got by simulating experiments. So, the feasibility and validity were proved.