Solving Maximum Clique Problem And 0-1 Planning Problem Based On DNA Origami

DNA is a polymer compound with a stable,regular double-helix structure.It has been widely studied and applied in many fields,because of its precise self-assembly ability,programmability of molecular sequences,and good biocompatibility.DNA computing is a new method of computing at the molecular level with the help of bio-molecular technology.It has the characteristics of high capacity and high parallelism.Meanwhile,It provides a new way to solve the NP problem.DNA origami is widely studied and applied in DNA computing,with programmability,dynamic adjustment and precise structural control.The main contributions in the dissertation are divided into three parts:Model one,In order to solve maximum clique problem,DNA origami system on DNA origami is established.The DNA origami system consists of three basic components:a DNA walker,two-state DNA machines and the origami tile.By the DNA strand displacement,DNA walker is rotated 120 degrees on the DNA template which is assembly by the two-state DNA machines and the origami tile to move and complete self-assembly.The hairpin structure on the DNA walker corresponds to the vertex of the graph,and whether the hairpin structure is unwrapped corresponds to whether the vertex is on the cluster.Fist,we encode the vertices in the graph and combine them into all possible cases.Then,using the DNA origami system to filter the solution.Finally,applying supplementary graph to observe the number of hairpin structures on the DNA walker by electron microscopy and obtain the maximum clique problem of graph.Model two,The product of DNA assembly is a linear duplex formed by the initiating duplex,and 'Chemistry' hairpins and 'Instruction' hairpins a staggered pattern.the duplex:one strand consists of instruction hairpins and the other of chemistry hairpins.By the DNA strand displacement reaction,strand migration occurs,and a growing oligomer is transferred to each hairpin,The sequence of assembly is programmed through interactions between pairs of complementary toeholds.Finally,the number of oligomers on the linear duplex is detected to read Maximum Clique of the graph and its vertices.Model three,In order to solve 0-1 integer programing problem,DNA origami system on DNA origami is established.The DNA origami system consists of two basic components:DNA origami template and four types of helper strands.After adding to input strands,gold nanoparticles(AuNPs)is selectively released of helper strands on DNA template by DNA strand-displacing.Observing gold nanoparticles is released in the DNA origami system or not by electron microscopy,meanwhile,reading the feasible.This structure method is simple to operate,easy to read,and can be used to create more complex systems.Figure[26]Reference[73]...