The DNA Computing Model Of 0-1 Programming Problem And Timetable Problem

Article" Molecular Computation of Solutions to Combinatorial Problems" written by Doctor Adleman was presented in the Science in 1994, in which a hard mathematical problem-Hamiltonian Path Problem was solved successfully using DNA molecules. Since then, a new discipline named DNA computing has come into being. The massive parallelism, high-density storage and energy efficiency of DNA computing attract the concern of numerous scholars from different fields. With the biological research method and experimental technique, the encoding problem and DNA computing model were mainly studied in this doctoral thesis. In DNA computing, the information is always represented by unique DNA sequences and its processing is accomplished through the special hybridization among those DNA sequences. Thereby the initial problem in DNA computing is the encoding problem, which belongs to the problem of NP substantially. At present, it is not perfect for the current coding method to satisfy the actual request of particular DNA computing models. Therefore, after simply introducing the encoding problem background and its research progress and summarizing the basic principle related to molecular biological DNA design, a method that utilizes computer software of biology to verify the encoding DNA was suggested in this thesis. Applied to an example that mentioned in this thesis, it was proved that the method is viable in verifying a small scale of DNA encoding problem by a late biological experiment. The development of the biologic technique plays an important role in the study of the DNA computing. In dealing with the information, an advanced biological technique—Biochip has the same characteristics comparing with the DNA computing. Accordingly three DNA computing models, the solution-based model, surface-based model and the combination of solution and surface-based model, were presented to solve 0-1 programming problem in the study. The advantages of massive parallelism, high-density storage and potential robotization of solution-based and surface-based model were well embodied and their shortages such as timewasting operations and less massive parallelism were also avoided by all means in these models. On the other hand, according to their common characteristics between the DNA computing and the biochip, the biochip is suggested to be a computational chip for the further DNA computer. Furthermore, the combinatorial model, which combines the advanced biologic technique with the DNA computing, could solve more complex programming problem. As a promising research field, the focus of DNA computation is whether it could solve a hard arithmetic (like NP-hard) problem in reality. It was recognized that the enhancing of capacity of computing by increasing the reaction vessel is meaningless for the development of DNA computing in theory unless the unexpected level of reaction can be performed. Using two kinds of biologic technique, AcryditeTM gel and Lab-on-Chip, two DNA computing models are proposed to solve a simple timetable problem firstly in this thesis. These DNA models were roboticized, subminiature and high-throughput though they cannot provide massive parallelism and high-density storage of a large reaction vessel. And we believe that developing a compact hybrid DNA computer that uses microchips by taking advantage of biological technique and DNA computing theory is helpful for a further research of DNA computing.