Application Of DNA Computing In NP Complete Problem

NP complete problem is a computational problem that is dificult to be solved perfectly by traditional Turing computer.The solution of this kind of problem increases exponentially with the increase of variables.For larger scale NP problems,the computing power of traditional Turing computers is limited.However,the high parallelism,high accuracy and high capacity storage of DNA computing give us a new way to solve the NP complete problem.Because DNA computing is not limited to linear computing like Turing machines,DNA computing is based on biochemical reactions,which are highly parallel and far more computational than traditional electronic computers.This paper studies the computational model based on DNA computation design to solve the NP-complete problems.Firstly,it summarizes the background knowledge of DNA molecules.At the same time,it introduces some classical problems of NP-complete problems,such as 0-1 integer programming problem,which can satisfy the problem,the largest group problem,etc.;then introduced some DNA calculation-based models designed by predecessors,and gave the model algorithm.Finally,based on the predecessor model,a DNA tweezers computing model is proposed,and the model is applied to solve the 0-1 integer programming problem and the SAT problem.After solving the 0-1 integer programming problem and the SAT problem,the logic gate operation is the basis for DNA computer.Therefore,at the end of the article,the operation of the OR gate is solved by using the DNA tweezers model.At the same time,strand displacement OR gate computing model based on DNA origami template is established,which showed the true and false results of the operation by fluorescence.Through the simulation of the Visual DSD,the computing model is highly feasible,and the mismatch phenomenon is rarely found during the reaction process.The application of the model in the larger combination logic gate will be possible.Figure[37]table[1]reference[44]...