Study On Some Theories Of Dna Computing

In 1994, Adleman solved a directed Hamilton path problem with DNA computing for the first time. Subsequently, prodigious progress has been gained on both theory and experiment research on DNA computing. In this thesis, the DNA computing models of boolean matrix multiplication and two NP-complete problems in graph theory have been built, and an optimization method is given on constraint variables of DNA sequence. The main results are as follows:Boolean matrix and its power are employed to convert and solve many problems based on mathematics models, for instance: automation state, switch question and so on. In this thesis, a new DNA algorithm of boolean matrix multiplication is given based on two boolean matrices and their product is represented by a directed graph. The number of short oligonucletides needed in the algorithm is equal to the size of directed graph. There is no PCR amplification step.The sticker model is based on the principle of Watson-Crick base complementarily match. It has three prominent advantages: memory strands require no extension, there is no enzyme on hybridization reaction and the memory strands can be utilized repeatedly. In 2005, Yang Chia-Ning gave a modified sticker model. The number of short oligonucletides in solving satisfiability problem is decreased obviously in the model. In this thesis, we modify the above model and build the DNA computing model of maximum independent set of graph. First, we convert the maximum independent sets of graph to the satisfiability problem. Then DNA algorithm for the maximum independent sets of graph is given based on the modified sticker model. The biochemical procedures are illustrated through an instance and the maximum independent sets of the graph are obtained.Vertex-coloring problem of graph is a well-known NP-complete one of graph theory. It has important applications in daily life. For instance: order problem, time-table problem, traffic state, vehicle maintenance, electrocircuit arrangement, and task assignment all have relations with vertex-coloring of graph. In this thesis, a new DNA sticker algorithm for vertex-coloring of graph is given based on the above modified sticker model. Firstly, a kind of memory strand is produced in bio-chemical reactions and the memory strands are used to generate DNA Memory complex representing all the possible vertex-coloring of graph in extremely short time. Then the ingenious extract operation is taken to detect the vertex-coloring solutions of graph. Finally, the DNA model is verified through a graph with 6 vertices and 8 edges. The number of short oligonucletides needed to encode vertices of graph is equal to the size of graph.In the DNA computing, constraint variables of sequence have not only the relativity, but also the redundant information. This brings inconveniently for the sequence analysis. In this thesis, we utilize principal components analysis of statistics to reduce the constraint variables of DNA sequence, obtain the new constraint variables (the principal component). Principal components are non-correlated each other, and they can reflect quite comprehensively the information of original constraint variables. Finally, we apply principal components analysis to the corresponding values of five constraint variables of ten DNA sequences.