Application Of DNA Computing Model In NP-Complete Problem

DNA computing is a popular subject It uses molecular biotechnology to solve problems in computer science or mathematics.It is a bridge between computer science and biochemistry.In the calculation of DNA,information is transmitted through the interaction between DNA molecules,and its process is completed by a series of biochemical reactions.Due to the large parallelism inherent in biochemical reactions and the high information density of DNA molecules,DNA is made Computing is slowly becoming an attractive and worthwhile area of research.This paper mainly studies the application of DNA computing in NP-complete problem.In the background knowledge,basic ideas and significance of DNA computing are firstly introduced.Then the application of DNA origami in the problem(SAT)is elaborated,and the research status of the satisfiability problem is listed.The satisfiability problem is one of the NP-complete problems that are of common concern in the fields of theoretical computer and artificial intelligence,and plays an important role in the NP-complete problem.Compared with some DNA self-assembly methods proposed in the past,DNA origami can be regarded as a new DNA self-assembly method.Using a calculation model based on DNA origami to solve the satisfiability problem,an example with 3 variables and 3 clauses is solved to illustrate the feasibility of the algorithm.The calculation model only needs to use gel electrophoresis to find a solution that the satisfiability problem.This is the most reliable biological operation known at present,which improves the feasibility of the model and reduces the difficulty of biological operation.At present,the results of using origami to solve the NP-complete problem are relatively few.The proposed method is a new attempt to solve the NP-complete problem by using biological DNA molecules.Although the SAT problem has many fruitful results,based on the importance of the SAT issue,the new method always attracts readers' attention.With the deeper research of the researchers,the structure and stability of DNA origami have been initially improved.As an emerging DNA computing model,it has played a certain role in promoting many aspects to provide greater help in the development of DNA computing.Based on the research status of the listed 0-1 integer programming problem,the application of giant magnetoresistance type DNA calculation model in 0-1 integer programming problem is proposed.In this paper,the variable of the problem is encoded into a DNA strand,the DNA probe is immobilized on the surface of the GMR-type chip,and then the biotin-labeled target DNA strand to be analyzed is sufficiently hybridized with the probe,and the nano-magnetic on the chip is passed through the on-chip GMR sensor.Bead detection,output as an electrical signal,to obtain a solution to the problem,avoiding distortion caused by signal conversion in fluorescence analysis.The model has higher sensitivity,simple signal detection and analysis,and lower requirements for signal detection equipment.Finally,the main research results of this paper are briefly introduced.The advantages and disadvantages of the proposed model and other DNA computing models are compared,and further research directions are explained.Figure[29]table[2]reference[58]...