Dissertation > Excellent graduate degree dissertation topics show

Resarch on DNA-based Algorithm for Several Problems in Graphic Theory

Author: GuoLi
Tutor: LiRenFa；LiKenLi
School: Hunan University
Course: Applied Computer Technology
Keywords: Ramsey numbers Isomorphism Minimum spanning tree problem DNA computing
CLC: TP301.6
Type: PhD thesis
Year: 2009
Downloads: 137
Quote: 0
Read: Download Dissertation

Abstract

Ramsey numbers, graph isomorphism problem, minimum spanning tree problem in graph theory problem in today's scientific research in many fields have a wide range of applications, with the expansion of the scope of its application, the solving of these problems is an increasingly large scale, but because solving The complexity of the algorithm for these problems is too high, greatly affect the applied research of such deep-seated problems. 1990s commenced, with Adelman's pioneering work in the field of DNA computing, DNA computing by virtue of its vast amounts of storage space with highly parallel computing ability, in theory, overcome the traditional computer storage and computing speed. has become one of the potential solutions for solving NP-complete problem in graph theory and other intractable problems. As biochemical technology continues to mature, the scale of the NP-complete problem can be solved on the theory and experiment is also growing. The DNA computer is not yet like the traditional computer universal DNA computer algorithms for solving a problem is difficult without modification applied to other similar problems, almost all based on DNA supercomputing algorithms are completely exhaustive way. The direct consequence of this way of the current \The issue has become a bottleneck to limit the application and development of DNA supercomputer algorithms. Both important polynomial time but also to overcome the number of DNA strand exponential explosion of new DNA computer algorithms and model study days, has become one of the important theoretical computer science research content, has considerable theoretical and practical significance . \DNA computer algorithms the problem three graph theory problem, and DNA biochemistry calculation process simulation verification. Ramsey theory is a huge and rich field of graph theory, set theory, logic, analysis, and has very important applications in algebra. The Ramsey Numbers solving is extremely difficult to solve the problem of the current scientific one. Adleman-Lipton model biological operations and paste the model solution space combined DNA computing model be extended, Xu Jin-bit sequence encoding method based on DNA computing model proposed a method for solving the Ramsey number algorithm. Algorithm is to start from the lower bound of each generation, until the upper bound, the solution of the problem space, then according to the definition of the Ramsey numbers, delete meet certain conditions for the solution of the final test tube, and finally detected, in order to determine the current value of the Ramsey number is required, which get a specific Ramsey numerical algorithm performance theory analysis and simulation results show that the theoretical possibility of this algorithm on the Ramsey numbers, at the same time, due to the use of a lower error rate of DNA computing models, and algorithms, the new misconception rate, the algorithm has a lower biological operation is also much simpler. On the basis of the above algorithm, using the divide and conquer algorithm design techniques, design a DNA computer algorithms Ramsey numbers based on divide and conquer, and the aforementioned algorithm, the operation time of the new algorithm is essentially unchanged, but significant reduce the number of DNA strands required by the algorithm, thereby expanding the scale of DNA computing can theoretically solve the problem of the Ramsey number. Graph isomorphism problem one of the classical NP-complete problem, Sun sticker model of DNA-based molecular computing algorithm based on further study of DNA computer algorithms Figure isomorphism problem, a model based paste and Adleman-Lipton the isomorphism DNA of the solution space computer algorithm, the algorithm using the degree of settle point Sequence concept, a simple arithmetic operation, in the worst case only O (2 ~ n), DNA chain number, where n is FIG. The number of vertices and maintaining biochemical number of operations of the algorithm is still polynomial order of magnitude. Minimum spanning tree is one of the widely studied problems in graph theory, has important applications background. Adleman model the biological operation with paste model-based solution space proposed for solving the minimum spanning tree problem DNA computer algorithms. The new algorithm generated by the solution space, edge subgraph Finder, the four parts of the Spanning Tree Finder and the minimum spanning tree search algorithm has m edges, n vertices, minimum spanning tree problem used in biological operand O (n ~ 2), the number of test tube is O (n), the maximum chain length of O (Mn) the DNA chain number of O (2 m), The. Due to the use of the error rate of the lower hybrid DNA computer model, the algorithm improves the spanning tree problem algorithm based DNA computing to solve the fault tolerance and accuracy.

Related Dissertations

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