The Research And Applications Of DNA Computing By Self-assembly

DNA computing is a new information processing pattern. It is different from electroniccomputer principle, as that electronic computer principle based on Turing idea, whileDNA computing based on biochemical reaction. Viewing from the ability of DNAcomputing to solve problems, it grows quickly. It only cost 15 years form an experimentgiven by Alderman in 1994, which can only deal with 7 vertexes HPP's computing todeveloping DNA computer to solve graph coloring problem, whose searching times are10²⁸ in 1997. Especially in recently years, a new theory and measure is provided for DNAcomputer's achievement, as the fast development of both the theory of DNA moleculeSelf-assembly and experimental technology. Given its vast parallelism and high-densitystorage, from theory, some shortages such as storage and operation speed in electroniccomputer can be overcome. DNA computing approaches show great potential to solvecomplex combinatorial optimization problems such as the NP-complete problems.DNA molecule self-assembly is a process, in which some molecules (such as DNA Tile)carry with input information, according to Watson-Crick complementary principle toproduce new DNA molecules, which have output information. The process develops underspecial temperature, concentration and enzyme. In this decade, the potential of DNAself-assembly has been widely developed in the fields of molecular computing, biophysics,nanotechnology and so on. It has important significance especially for the development ofDNA computing. DNA computing by self-assembly model completes the computingprocess by using DNA molecules' autonomously associate with each other to formsuperstructures. The idea of computing aroses from the combination of DNA computing,the theory of tilings, and DNA nanotechnology. So it has become one of the remarkablemodels. During the computing, it avoids too much experiment operations, time consumingand error, while other DNA computing models can not. This paper mainly focuses onDNA computing by self-assembly. Discussing DNA computing by self-assembly'sapplication both in NP-complete problem and information safety field, and an encodingdesign scheme is proposed. The detailed contents are as follows.Subtraction and division are fairly basic operators for any computing model. This partshows how the tile assembly process can be used for subtraction and division. In order toachieve this aim, four systems, including the comparator system, the duplicator system, the subtraction system, and the division system, are proposed to compute the differenceand quotient of two input numbers using the tile assembly model. This work indicates thatthese systems can be carried out in polynomial time with optimal O(1) distinct tile types inparallel and at very low cost.0-1 integer programming problem, an aspect of linear programming, has been playingan important role in the field of modern engineering research. This paper provides a DNAcomputing model by self-assembly for 0-1 integer programming problem. The basic ideais to use combinatorial chemistry techniques to simultaneously generate all potentialsolutions and then to filter them, based on chemical properties related to the informationthey encode, leaving at the end possibly only some molecules that have all of the desiredproperties. Finally, we obtain the solutions of the 0-1 integer programming problem.As is well known, the graph coloring problem is an NP-Complete problem. Consider aparticular coloring to the vertices in a graph. On a conventional computer, it is fairly easyto check whether this particular coloring is a solution to the problem. In fact, this can bedone in time linear to the size of the graph. It is the huge (exponential) number of differentcolorings that makes the problem difficult. This work proposes a way to perform thischecking procedure on molecular substrate using 2D DNA self-assembly. All checks couldbe done in parallel by an exponential number of computers, completing the wholecomputation in linear time.The part shows how the DNA self-assembly process can be used for breaking the RSAand NTRU public key cryptosystems. The security of RSA is based on the difficulty offactoring the product of two large prime numbers. In order to break RSA and NTRU, amethod for implementing the product of two primers or the cyclic convolution product oftwo polynomials using self-assembled DNA computing is expounded. Then, we provide anon-deterministic algorithmic to break efficiently the two public key cryptosystems. Bycreating billions of billions of copies of the participating DNA tiles, the algorithmics willrun in parallel on all possible solutions. The computation takes advantage ofnon-determinism, but theoretically, each of the non-deterministic paths is executed inparallel, yielding the solution in time linear in the size of the input, with high probability.It presents clear evidence of the ability of molecular computing to perform complicatedmathematical operations.In DNA computing the quality, quantity and the length of DNA sequences exhibit astrong association with the efficiency, reliability, and scalability of DNA computing. Theselection of proper DNA encoding constraints parameters is the key factor to improve the effection of the DNA computing. DNA encoding sequences design is a bothersome task asthe encoding problem is an NP problem. It is computationally difficult because the size ofthe solution space-all possible sets of sequences of the specified length and size-can beenormous, and there is no known efficient procedure that is guaranteed to find optimalsequences even for the simplest design criteria. Here, a novel heuristically DNA sequencesdesign algorithm is proposed, which is based on nearest neighbor thermodynamic modeland can generate a set of DNA sequences with uniform melting temperature. In addition,these DNA sequences satisfy minimal free energy constraint which prevents theinterference between different DNA molecules, and improves the reliability andeffectiveness of DNA computation. Furthermore, the DNA sequences generated by ouralgorithm are compared with the sequences generated by Deaton's algorithm. The resultsshow the efficiency of our algorithm and validate the algorithm rationality.