The Study On Some Theories And Applications In Four Types Of DNA Computing Models

In the thesis, some theories and applications in four types of DNA computation models are studied and discussed. The main results are summarized as follows:The sticker system is a language generative mechanism based on sticking operations and a DNA computation abstract model that follows Watson-Crick complementarity relation to anneal. In this dissertation, the sticker systems of linear string are extended to bidirectional sticker systems with complex structures, which makes the pure theoretical study step forward to biologic operation techniques. The definition and basic operations of bidirectional sticker systems with complex structures are given out. The classifications of bidirectional sticker systems with complex structures are proposed. The generative and computational capacities of bidirectional sticker systems with complex structures are discussed. Finally, the characterization of recursively enumerable language is presented by means of weak coding of the above systems, which means that bidirectional sticker systems with complex structures have the same computational capacity as the family of recursively enumerable languages.The sticker model has a random access memory and its DNA strands have a fixed length. The operations require no strands extension, use no enzymes, and its materials are reusable in theory. In the dissertation, DNA sticker algorithm of vertex-coloring problems is given out. When the vertex-coloring problems of graph being studied, they are decomposed into vertex-independent set problems and vertex-partition problems from the essence of problems and DNA sticker algorithms of the two problems are showed; Then the vertex-coloring problems of graph are solved by transferring the above two algorithms. In 1965, M.Behzad and Vizing proposed the Total Coloring Conjecture of graphs. So far, for any graph, the Total Coloring Conjecture is still an open problem. In this dissertation, the total chromatic number of series-parallel graphs of maximum degree greater than or equal to will be determined using the double inductions and the techniques of exchanging colors from the aspect of configuration property.The splicing system is a language generative mechanism based on splicing operations, where splicing operations are the mathematical abstractions of DNA strands recombinant behaviors under restriction exonucleases, endonucleases, DNA ligases and DNA polymerases. In this dissertation, the ideas of simulating directed Hamilton path problems by splicing 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 splicing systems. In our construction, the splicing systems simulating problems run at most steps, where is the size of problems.The minimal vertex-covering problem of graph is a NP-complete problem of graph theory. It may apply widely to molecular biology, schedule problem, error diagnosis, the balance of resume and collection, the journey plan of oil tanker and switch theory. In the dissertation, the minimal vertex-covering problems are studied from the point of computational models based on surface. In the DNA computational models on surface, after a data pool being constructed corresponding to the subsets of a vertex-set of a graph with vertices and edges, a series of biochemical experiments: synthesis, hybridization, cleaning and denaturalization etc are proceeded and the DNA sequences corresponding to all the coverings are obtained; Then all the minimal coverings according to the encoding address procedure are listed. After all, the built models are verified by a graph with vertices and edges.