Research On DNA Computing Model Based Sticker System

Since doctor Adleman successfully gave the solution of directed Hamilton path about directed graph with DNA computing in 1994, there have been significant research efforts on the DNA computing and the DNA computer. Prodigious progress has been gained on both theory and experiment. In this dissertation, some results have been made on DNA computing and DNA computer by way of building DNA computing model of some problems about the graph theory and combinatorial optimization.DNA computing is a new calculation method that used biological molecule DNA as calculation medium and biochemical reaction as calculation tool. The basic theory of DNA computing is: Encode information using the special structure of DNA double helix and nucleotides match rule, and mapping the object to operating to DNA molecules strands, and under the control of enzyme building a data pool, then using the rules appointed mapping the DNA molecules strands to a high speed parallel data computing bio-chemistry procedure. At last, using molecule biology technoly such as polymerization chain reaction (PCR), ultrasonic degradation, clone, trap, molecules purify, electrophoresis, magnet-bead separate and so on, detect the result of the reaction. The appealing characteristics of DNA computing are vast genetic codes of DNA molecules as well as massive parallelism of bio-chemical reactions. Therefore, new generation of computer based on DNA computing model (so-called DNA computer) features vast memory space and fast running speed.In this paper, the main computing model, including surface-based, plasmids, sticker and molecular beacon computing models were thoroughly introduced, from conformation of DNA molecules point of view.The sticker system is a language generative mechanism based on sticker operations, where sticker operations are the mathematical abstractions of DNA strands recombinant behaviors under restriction exonucleases, endonucleases, DNAligases and DNA polymerases. In this dissertation, the ideas of simulating directed Hamilton path problems by sticker systems are designed using their massive parallelism; Then some properties of directed graphs and sufficiency and necessity conditions of existing Hamilton paths in graphs are presented based on the analysis to directed Hamilton path problems according to the properties of languages generated by the sticker systems.In our construction, the sticker systems simulating problems run at most n-1steps, where n is the size of problems.