Research On Combinatorial Optimization Problem Based On DNA Self-Assemble

DNA computing is a cross-cutting technology based on many disciplinary. It depends on the development of Molecular biology and Computer science. By virtue of high-density storage and massive parallelism in DNA sequences, the calculation model has showed a great advantage in solving complex combinatorial optimization problems and NP hard problems. In recent years, many researches on DNA computing have been made, and some models based on DNA computing have been put out, such as: splicing system model, tile self-assembly model and sticker model. Researches on DNA self-assembly model attract more and more experts and scholars because of its simple operation and no human interference during the process. DNA tiles self-assembly model is a process, during which DNA tiles produce new DNA molecules that have output special information needed according to Watson-Crick complementary principle. It puts DNA computing, Ting theory and DNA nanotechnology together. This thesis is as follows:Firstly, some basic background knowledge on DNA computing and DNA self-assembly and the present researches and development on them are introduced. The advantages of large scale parallelism, ultra-low power consumption and ultra-high density storage make the DNA computing become a hot, and its further development will facilitate the existing methods. Secondly, many studies and discussions on three typical combinatorial optimization problems are made by taking DNA computing self-assembly model as a means, and NP problems as the researched object. Some computing tiles are constructed, results are obtained and some analyses are made on computational complexity for each problem.For the 0-1 knapsack problem, the previous method has been improved and a comparison system constituted by DNA Tiles is introduced, which is used to judge constraint conditions whether met or not by the system. The method improves the time complexity compared to the previous method, and this problem can be solved in polynomial time in theory in this thesis.Bin packing problem is also a typical combinatorial optimization problem, and the method for the problem in this paper is only for one dimension. The idea of Binary method for grouping is introduced in the problem and a subtraction system is used during the self-assembly. The model provides a new idea for studying more complex problems.Degree-constrained minimum spanning tree problem is a classic problem in graph theory, and the purpose of the problem is to find out minimum spanning tree meets the requirement of degree in a given graph. For solving the problem, an idea of nondeterministic search is introduced and some operation rules and tiles are set, the problem is solved successfully. Finally, the idea is made some promotion to TSP (traveling salesman problem), and provides a new way for studying the problem.Finally, the summary and prospect of DNA self-assembly are made in the paper. The research and application of DNA computing is still at the beginning as a new emerging discipline, and it needs further study and discussion since there are some shortcomings both in theory and implementation of technology.