Research On Some Problems Of Chain Replacement Model

In recent years,DNA computing is gradually developing as a new interdisciplinary subject.DNA computing is a new method of computing the structure of biological molecules DNA through the corresponding biological technology.Using the DNA computing model as the background and the large storage capacity and high parallelism of DNA,a new generation of computer is designed.So the DNA computer is also a complete form of information technology established by DNA,using the coded DNA sequence as the operation object,using the operation of biological subsystem,to obtain the final target DNA chain,and to solve the problem of the problem biological computer.The basic idea of DNA computing is to solve the computer problems with molecular biotechnology and control the operation process.DNA computing models include paste model,plasmid model,double stranded DNA model and so on.At present,as one of the hotspots of research,DNA computing technology in DNA information processing field has the advantages of good parallelism,low energy consumption and high preservation.Therefore,it has been applied to various complex computing problems.The emerging field of DNA nanotechnology has also developed rapidly,among which DNA chain replacement is attracting much attention due to its self induction,sensitivity,accuracy and simple operation.This paper introduces a biological computing method based on DNA chain replacement.It is a calculation method without manual intervention.The model can use logical formulas to perform iterative resolution steps in the connection paradigm.The implementation of this method is based on DNA chain permutation technology,each clause is encoded in a single DNA propositional proposition,and is encoded as the different propositions of each proposition and its complementary chain to the propositional clauses in the same chain.The model allows the logic program composed of Horn clauses to run through cascading parsing steps.The potential of the model is also reflected in its theoretical ability to solve the SAT.The result of the SAT algorithm has a linear time complexity in the number of solving steps,and its spatial complexity increases exponentially in the number of variables.This paper summarizes the five recent developments of the DNA chain permutation in DNA Computing:(1)cascade circuits;(2)catalytic reaction;(3)logical calculation;(4)DNA calculation on the surface;(5)the logical calculation of nanoparticles based on chain substitution.This study first introduces several new biotechnologies involved in the current computing field,focusing on the technology involved in this study,and then uses chain permutation to solve the maximum matching problem,the small vertex cover problem and the postman problem.First,taking DNA computing as the research background,we discuss the research significance and development prospect of DNA computing.Second,for all the edges set in the graph,find the maximum edge set of any two edges without common vertex in the graph,which is a NP complete problem.The algorithm simulation for solving this problem converts the mathematical problem to the DNA chain,encodes each edge of the given graph by using the characteristics of DNA,and the corresponding biobo In this work,we use chain replacement technology to separate the target chain.This chain represents the solution.Through experimental operation,the solution of the maximum matching problem based on chain replacement is given,which proves that the algorithm is effective and feasible.Third,in order to solve the minimum vertex cover coverage problem in DNA computing,this paper uses the delete operation of the data pool representing the empty solution,finds the complement of the solution,and obtains the optimal solution of the problem.On the basis of chain replacement,instead of enzyme,the efficiency and time saving of experiments are improved.This algorithm is unique,novel,simple and reliable.Fourth,the typical knapsack problem in combinatorial optimization is a very important NP problem.Aiming at the 0-1 knapsack problem,this paper uses the algorithm that converts the mathematical problem to the DNA chain,encodes the volume and value of the given item,and does not join the ligase.According to the W-C principle of the DNA chain,the required DNA chain is used respectively.In the process of short chain connection,and in the process of reaction,adding foreign chain to get the combination of items satisfying the constraints,using chain replacement technology and the corresponding biological operation to delete the exogenous DNA chain,and the separation of the final chain,and give the calculation method of the 0-1 knapsack problem based on chain replacement.The proposed algorithm is effective and feasible.Fifth,the mailman's walking route is described in the language of graph theory.In this paper,the algorithm is used to transform the mathematical problem to the DNA chain,to encode every edge in a given graph G,and to encode the DNA chain that connects the DNA chain,generate the solution of the problem,and the corresponding biological operation to separate the final chain.Sixth,the DNA coding method is designed in this paper,and an algorithm for solving the problem of Chinese postman with 6 vertices is designed to prove that the proposed DNA calculation method is effective and feasible.