Resarch On DNA-based Algorithm For Several Problems In Graphic Theory

Such graphic theory problems as Ramsey Number problem, Graph isomorphism problem, Minimum Spanning Tree problem, are being widely applied in various research areas. As the range of its application expands the scale of solving these problems become larger and larger. The high complexity of algorithms which solve these problems results in a negative impact on the applications of such problems. In the 1990's, after DNA computing war first proposed by Adelman, because of its massive storage and capability of highly parallel processing, theoretically DNA computing can overcome the drawbacks of traditional computers on storage and processing speed, and consequently becomes one of potential solutions to NP complete and other hard problems. As biochemical technology turns mature, the scale of NP-complete problems which can be solved by DNA computing in theory and pratice is much more larger.However, different from the traditional computers, DNA computers are less universal than traditional ones, so the algorithm or a DNA computer just for one kind of problem can not be transplanted to solve other problems without any modification. As a result, almost all the current DNA based algorithms and models take the brute-force method, which directly leads to rapid increase of DNA strands with larger scale arithmetic. Besides, the problem of exponential explosion of solution space become more and more outstanding using brute-force method, which places a bottleneck on the way of application and development of DNA computing.Hence, it is more important to research on DNA algorithms with polynomial time complexity and no exponential explosion problem, undoubtedly research on this new DNA based algorithms means a lot in theory and practice.In this thesis we center around solving exponential explosion problem in DNA computing, deeply investigate features of biological operations in DNA computers. We introduce policies, methods, and technologies of parallel processing of current electronic computers into DNA computing, and for Ramsey Number problem, graph isomorphism problem, and Minimum spanning tree problem, propose novel and improved DNA-based algorithms or models respectively, followed by simulation of their biological operation process.Ramsey theory is a large and rich field, and plays an important role in set theory, logics, analysis, and algebra. Ramsey number problem is one that is quite hard to solve. Extending DNA computing model which combines biological operations in Adleman-Lipton model with solution space in sticker model, based on bit sequence coding method proposed by XuJing, we come up with a new DNA computing model and algorithm for Ramsey number problem. The algorithm generates solution space, starting from bottom boundery to top boundery, and then cancels solutions satisfying certain conditions according to definition of Ramsey number, at last detects the final tube to make sure whether it is the Ramsey number to obtain. Theoretical analysis of algorithm performance and results of experiments shows the feasibility of solving Ramsey number by our algorithm. Meanwhile, because a DNA computing model with lower error rate is used, compared to the similar algorithms, ours has lower error rate and simpler biological operations. On basis of last algorithm, we design a DNA algorithm to solve Ramsey number problem using division and conquer method. Compared with the last algorithm, the new one keeps the same operation time,but dramatically decrease DNA strands, as a result, enlarge the scale of theoretically solving Ramsey number problem by DNA computing.The graphic isomorphism problem is one of classic NP-complete problems. On basis of DNA computing algorithm based on sticker model proposed by Sun, we make further investigation on DNA computing algorithm for graphic isomorphism problem. And propose an algorithm based on sticker model and solution space of Adleman-Lipton model. It makes use of incidence degree sequence of nodes. Our algorithm has simple operations and requires only O(2~n) DNA library strands in the worst case, where n is the number of vertex in graph. Biochemical operations keeps polynomial.The minimum spanning tree is one of problems widely researcdhed in graphic theory, which has important application background. We propose a DNA computing algorithm for minimum spanning tree on the basis of biological operation in Adleman model and solution space in sticker model. The new DNA-based algorithm to solve Minimum Spanning tree problem consists of Solution Space Generator, Parellel Searcher, EdgeInduced Graphics Generator, and Spanning tree Searcher. For minimum spanning tree with m edges and n vertex, the number of biological operation is O(n~2), the number of test tube is O(n), the maximal length of strand is O(m + n), the number of DNA strands is O(2~m). Because of using DNA computing model with lower mixed error rate, our algorithm improves performance on fault-tolerance and accuracy.