Application Of DNA Origami In Solving 0-1 Integer Programming Problem

DNA origami is a new self-assembly method that has been proposed in recent years.The most important idea is to fold a long DNA single strand(scaffolding chain)into a specific shape to complement each other by using many designed short DNA single strands.DNA origami is widely used in DNA computing due to its advantages of programmability and nano-addressability.The 0-1 integer programming problem is one of the NP-complete problems,which is a special case where the variables in the integer programming problem are only 0 or 1.At present,there is no particularly good algorithm to solve this problem.One of the current difficulties is how to design efficient algorithms to solve 0-1 integer programming problems.The combination of the nanostructure constructed by DNA origami and the huge parallelism and massive storage capacity of DNA computing can avoid the number of experimental operations in the calculation process,reduce the time consumption and error solution rate,which thus provides an effective way for effectively solving 0-1 integer programming.This dissertation firstly introduces the state of art of DNA computing and the common biotechnology,and then proposes the common DNA computing models.On the basis of predecessors,a calculation model of 0-1 integer programming based on DNA origami is proposed.We apply the DNA tetrahedral walker to solve the 0-1 integer programming problem,and find all possible solutions by the walking of the DNA tetrahedral walker.Finally,we determine whether it is a feasible solution to 0-1 integer programming problem by using the number of gold nanoparticles carried by DNA tetrahedron walkers.The proposed model has a low error rate and strong controllability and practicability.Meanwhile,we apply DNA tetrahedron probe to solve 0-1 integer programming problems,which utilizes DNA tetrahedrons combined with DNA single strands to construct probes to reduce the rate of error in biochemical reactions during the solution process,and thus improving the computational efficiency of the model.This dissertation also extends DNA origami to solve the 0-1 knapsack problem.We employ DNA origami and hybridization chain reaction to construct a computational model of the 0-1 knapsack problem.The proposed model anchors 9 hairpin structures and 1 molecular beacon on a DNA origami substrate and adds sufficient auxiliary chains.The hybridization chain reactions on different paths can be triggered by adding different initiating chains,which can obtain all possible solutions of the problem.the feasible solution is determined by the number of fluorescent signals,which thus finds the optimal solution of the problem.The model was also simulated by Visual DSD software,and the results show the good feasibility.Finally,this dissertation also proposes a calculation model based on the satisfiability of DNA strand replacement and DNA origami.First,we map all solutions to the satisfiability problem onto an origami substrate;Secondly,the initiator chain is added to allow it to respond adequately.At last,the feasible solution was determined by the fluorescence on the DNA origami substrate such that searching for the final solution of the satisfiability problem.Figure[34]table[2]reference[54]...