Research Of Several NP-complete Problems Based On DNA Computing Models

DNA computing, which is also called, is a completely new calculation model which is based on Biochemistry Reaction. DNA computer is much better than traditional transistor computer as for complex NP-complete problem, for example, highly parallelism, huge data storage, extraordinary low energy consume, quick run speed. Consequently the research of DNA computing methods and theory has great significance to the realization of molecular computer. Recent researches also show that DNA computing has the great potential and good prospect in the specific complex area.In 1994, professor Adleman in South California University solved the Directed Hamilton Path with seven points (DHPP) Problem using biochemistry experiment. Form then on, DNA computing rapidly becoming the active scientific research field, and the research of DNA computing is also developed in many countries. The contents involved the DNA computing models, the algorithm some NP problems, data encryption, intelligence control, DNA data storage, the complexity of DNA computing, molecule high-level language, the combination or integration of DNA computing methord and all sorts of soft science and etc. Although a lot of the researches have already got plentiful achievements, most of them remained on theoretical degree Because researcher not only get the limitation of across mutil-subjet, but also the difficult build on experiment condition due to the complexity of biological experiment. Only in theoretical research field of DNA computing, there are many DNA algorithms of several classical problems on graph, combinatorics and mathematics. There are DNA algorithms of some problems, but still to be improved.However, studying on DNA computing is to build the DNA computer of great application value. So, to DNA computing, experiment manipulation, experiment equipment, experiment condition and combination in theory and practice are of great importance, which is also the direction of further study.Sticker model and splicing model are two of the important DNA computing models. Sticker model is a universal computer system. Peer computing capacity to splicing model, 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.The paper solved some difficult NP-complete problems, according to the sticker model of DNA computing, and simulated the algorithms of the experiment.(1) A DNA algorithm based on Adleman model for Hamilton problems was proposed to solve Minimun Vertex Cover Problem in detail. At first, the algorithm produces all satifiable results of the SAT problem, then, right results are straightly separated among these results. In this way, the experiment efficiency and results accuracy are greatly advanced.(2) To a classical logic calculus problem, using the ideal which Lipton solved the SAT problem, we proposed a DNA algorithm based on sticker model. By improved algorithm, problem is transformed corresponding open-close network graph and contact network graph. Further, thoughtway of solving Discrete Mathematic problems is broaded greatly by use of DNA computing.(3) Sticker system is a abstract model which use the Watson-Crick complementary principle in DNA computing, it is also a language generator based on sticker calculation. Traval Salesman Problem was convert into a problem of seeking the Hamilton cilcle of the smallest weight in graph, this way solved the NP-complete problem and further improved the coding.In solving the above problems, detailed model, coding and prescription of the methods are presented and correct answer of TSP are obtained through simulate experiment. Thus the feasibility and validity of the algorithm is proved.Statement: Because DNA computing relate to biological experiment, this paper make emphases on theoretical research by the limitation of experiment environment. Please you make understanding.