Research On DNA Computing Model And Experiment For Graph Vertex Coloring Problem

DNA computing is a novel computation paradigm with DNA molecules as"data", and biochemistry trials as"information processing instruments". Because of its massive parallelism, high-density storage and energy efficiency, DNA computing attracts the concern of many scientists with different backgrounds. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. However, many issues still exist in DNA computing. It is important and interesting for further study on DNA computing.The graph vertex coloring problem is the main topic of graph theory and applied in many fields, which is known as NP-complete problem. In this dissertation, with the biological research method and experimental technique, four effective, reliable DNA computing models to solve this problem are proposed. The advantage and disadvantage of these DNA computing models are discussed. The main research works are as follows:An enumerating DNA computing model based on hybridization reactions is proposed. The graph vertex coloring is encoded by DNA molecules and solve by hybridization reactions and polymerase chain reaction. To testify this DNA computing model, a graph with five vertices is designed and the relevant biochemistry trials are completed. The results show that this model can solve vertex coloring problem efficiently.To reduce the number of encoding, an improved enumerating DNA computing model is presented, which is based on enzyme digestion reactions. The graph vertex coloring problem is encoded by double encoding method, and the false solutions deletion and the true solutions detection are updated and automized partly after enzyme digestion reactions and polymerase chain reaction.The solution space exponential explosion problem is the biggest obstacle in DNA computing. To overcome this problem, a non-enumerating DNA computing model is designed and testified based on the optimization of encoding method and construction of initial solution space. Polymerase chain reaction and Sequencing technology are used for delete false solutions and true solution detection in these models. This DNA computing model is used for solving vertex 3-coloring problem of a graph with 12 vertices. The results of the biochemistry trials show that many false solutions can be deleted when constructing the initial solution space, which overcome the solution space exponential explosion problem and improve the computational efficiency.To solve large-scale graph vertex problem, a parallel type of DNA computing model is proposed based on the development of the non-enumerating DNA computing model. The method and principles of subgraph division are studied to implement the parallel procedure. To testify its computing capacity, a graph with 61 vertices is testified. The results indicate that this model extends the advantage of the first non-enumerative DNA computing model, improves the computational efficiency, and reduces costs significantly, which can be used for NP problems in a larger scale.To get enough encodings for different DNA models, many constraints and parameters are considered and given. The rich encodings can form a database for design and application of DNA computing technology. The experiment results prove that these encodings are qualified and can avoid the error in experiments. The database can benefit further researches in the field of DNA computing.