The Research Of Molecular Algorithm Based On NP Problems

DNA algorithm is a new method that simulates the molecular structure of DNA with thehelp of biological molecules. Molecular algorithm as a new discipline develops gradually.The advantage of resolving the number of huge parallel computing and NP-completeproblems is obvious.In 1994, Adleman for the first time successfully a seven-node solved Hamiltonian pathproblem using molecular algorithm through test-tube experiments. The experimental procedure of DNA algorithm is: As the molecular structure of DNA double helix and nucleotidesmatch, so we can map the object to DNA strands. Enzyme catalysis forms different data pool,then the initial data maps to a biochemical operation that is easy to control. Finally using pol-ymerization chain reaction ultrasonic degradation ,hybridization ,clone,trap,molecules puff,electrophoresis, magnet-bead separate and so on ,detect the result of the reaction．This article is divided into three parts introduced DNA algoritm for solving NP-completeproblems.The first part gives a method to solve single restriction not 0-1 integer knapsack problemwith DNA computation. DNA encoding for all values of any variable were applizd and allpossible solutions were synthesized．And all optimized solutions were filtered out using groupinsert experiment and group delete experiment.Finally all optimization solutions were foundusing detect experiment．And an example explains the feasibility of the DNA algorithm.In the second part, DNA computing has recently generated much interest as a result ofpioneering work by Adleman and Lipton．Their DNA algorithm s worked on graphrepresentations but no indication was provided as to how information on the arcs betweennodes on a graph could be handled．The aim of this paper is to extend the basic DNAalgorithmic techniques of Adleman and Lipton by proposing a method for representing simplearc information—in this case, distances between cities in a simple map．It is also proposed that the real potential of DNA computing for solving computationally hard problems will onlybe realized when algorithmic steps which cuently require manual intervention are replaced byexecutable DNA which operates on DNA strands in test—tubes．The third part gives a new calculation model for solving the shortest path problem.