Research On The Model Of Satisfiability Based On DNA Computing

Satisfiability problem is a classical mathematical problem with a long life.SAT problem is generally called the satisfiability problem of propositional logic.Deterministic algorithm and nondeterministic algorithm are two algorithms to solve SAT problem.If a Boolean expression is assigned a proper logical value,the formula can be true,then it is said that the formula is satisfiable.According to the given formula,the problem of Boolean satisfiability can be detected.This decision problem is very important in every field of computer,including computer science,algorithm,cryptography,artificial intelligence and complexity theory.Modeling is suitable for most of the satisfiability problems.High capacity storage,high accuracy of the results,and high parallelism are the key points.All of these are the advantages of DNA computing,which makes DNA computing take advantage in solving the satisfiability problems.The computational model of satisfiability problem is the focus of this paper,and the design of these models is the preparation for DNA computing.This paper is mainly divided into four parts.The first part introduces the common operation technology in the experiment,and briefly describes some basic knowledge of DNA computing.The second part introduces the basic knowledge of the satisfiability problem.The third part is the main part of the article,and introduces two different DNA origami computing models.The fourth part is the summary of this paper.The third part is the main work of this paper,which introduces two models of DNA computing based satisfiability problem.In the first one,a computational model of the satisfiability problem based on DNA strand replacement is established.The constraints of the satisfiability problem are mapped to the number of fluorescence on the computational model.Two values(0 and 1)of variables in the satisfiability problem are designed into different DNA strands respectively.Through the DNA strand replacement reaction,the feasible solution to the satisfiability problem can be found through observation Observe the number of fluorescence on the calculation model after reaction.The second calculation model is a dynamic DNA origami structure,which is composed of three parts:DNA origami card slot,two-state DNA machine and DNA walking robot.The origami card slot is composed of a long DNA strand and several short strands.The DNA walking robot is a three handed and four legged DNA origami structure composed of seven single strands.The two-state DNA machine can control the valve to open or close,and the result is whether it carries fluorescent particles.The "hand" of the DNA robot receives the fluorescent particles carried by the DNA robot through the chain replacement reaction with the two-state DNA machine.The "foot" of the robot is driven by the chain and rotates 120 °clockwise on the origami base assembled by the origami card slot and the DNA two-state machine to complete the dynamic walking.According to the constraint variable of the problem,we can selectively receive the fluorescent particles.Each step corresponds to the value of a variable.We map the problem with the number of fluorescent clusters and the solution of the problem with the color of the fluorescent clusters.Both models have the characteristics of simple operation and easy observation and detection,which greatly improves the feasibility of the model and the accuracy of calculation.Figure[27]refer[51]...