Research Of NP-problem Based On DNA Computing

The DNA computing is a new method that simulates the structure DNA of biology molecule and does the computing by molecule biological technology.The DNA computing mainly divides into two steps:First step produces all possible solutions of the question and next step does Solution examination.It is an emerging interdisciplinary studies that develops gradually. It has inestimable superiority in solving in the massively parallel estimation problem, specially in solving in a NP complete problem.In 1994, Adleman has solved Hmilton way problem in the graph theory using the DNA computation, and has done the experiments successfully. Tts goal is to produce a new generation computer which takes the DNA computing model as the background and has the magnanimous memory genetic code and the extremely quick running rate. 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 underthe control of enzyme build a data pool, then use the rules appointedmapping the DNA molecules strands to a high speed parallel data computingbio-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 let the encoded DNA strands as input, and in test tube or other carrier take place specificbio-chemistry reactions controlled, then achieve the computing procedure to give the whole result space after the reaction. In DNA computer system, the codes in DNA molecules can be look as data in memory, after through the enzyme work towards DNA molecules to achieve some kinds of reaction instantly, the code could be transformed from one to another. Then DNA computing is a progress that by the abundant exact under controlled chemistry reaction towards DNA helix including tag, amplify or destroy original strands to achieve different computing progress.From using DNA molecular structure by DNA computing, this has introduced DNA code question presently and application to the solution of the NP-complete question.To Aim at the TSP question,it has used the DNA sequence to express realization algorithm by three ways: the weight size, the melting point temperature controlling code and stick system. This article has proposed one kind DNA computing model of the smallest apex cover question based on satisfing the solution space. Using the way of stick model in processing knight question, and it took the DNA chain as the physical foundation of information expression, whose computing based on the complement code changing rule of Watson-Crick.