Dissertation > Excellent graduate degree dissertation topics show

Study on Some Theories of DNA Computing

Author: XueShengWei
Tutor: WangShuDong
School: Shandong University of Science and Technology
Course: Applied Mathematics
Keywords: DNA computing NP-complete problem sticker model boolean matrix maximum independent set of graph vertex-coloring of graph constraint variable
CLC: TP301.6
Type: Master's thesis
Year: 2008
Downloads: 11
Quote: 0
Read: Download Dissertation

Abstract


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.

Related Dissertations

  1. Research on Combinatorial Optimization Problem Based on DNA Self-Assemble,TP399-C8
  2. Course Scheduling System Research and Implementation of Multi-campus credit system by genetic algorithm,TP18
  3. Design and Research of the data structure in DNA computer,TP311.12
  4. The Research on Several Problems of DNA Computing,TP301
  5. The Solutions of a Fuzzy Relation Equation in a Complete Brouwer Lattice and the Problem on the Number of Transitive Relations,O159
  6. The Design and Implementation of DNA Computing Model Based on 0-1 Programming,TP3
  7. The GA in the DNA Computing of the Research and Application,TP18
  8. The Application of DNA Computation in Information Security,TP309
  9. The Coding Sequence of DNA Computing and Algorithm Theory,O157.4
  10. The Research and Application of DNA Computing by Self-assembly,O242.1
  11. The Design of Boolean Logic Gates Based on DNA Computing,TN79
  12. Arithmetic Operation by Biological Technology,TP301.6
  13. Wireless Sensor Network of Minimal Set Covering of DNA Algorithms,TP301.6
  14. Multiuser detection techniques based on DNA computing and genetic algorithms,TN929.533
  15. Good point- set genetic algorithm theory and application,TP18
  16. DNA Algorithm for Traveling Salesman Problem Based on Molecular Computation,TP301.6
  17. A Study of the Algorithm and Computational Complexity for a Type of TMF Scheduling Problem,O223
  18. Research of Multicast Routing Algorithm Based on Agent,TP393
  19. Theory and Algorithm for the Problem of Curriculum Schedule Arranging,O157.5
  20. Study of Distributed QoS Routing Algorithm,TP393.01

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net  Mobile