| DNA computing is a new computing paradigm. It computes with DNA strands as materials, and biochemistry experiments as tools. DNA strands have huge storage ability of message; and DNA computing has tremendous parallelism that other computing paradigms can not catch up with.Researches on DNA computing had been spread out since 1994 when professor Adleman in South California University solved Directed Hamilton Path problem of a graph with seven vertexes by biochemistry experiments. Researchers had made a big progress, but theory research was a big bulk. Researches on operations and experiment equipments were scarce. There are still no DNA algorithms of several classical problems about graph and mathematics. DNA algorithms of some problems had been existed, but still to be improved.Sticker model and splicing model are two of the important DNA computing models. Peer computing capacity to splicing model, use of fixed-length DNA strands, free of enzymes and strands expanding, repeated use of materials caused researches on sticker model making a rapid progress, and DNA algorithms of many problems were proposed, too. But operation steps were excessive, and precious time was exhausted since only four basic operations of sticker model were adopted in experiments. For the reasons above, not only the concept "multi-separation" but also a multi-separation equipment model was proposed. Multi-separation as well as many basic operations in DNA computing could be carried out with this equipment. So, the operation steps were reduced, and the efficiency was improved. The following problems were solved with multi-separation techniques in this thesis.(1) The knight traversing problem. A DNA algorithm based on Adleman model was proposed to solve the knight traversing problem on expanded chess board. The problem could be solved with basic separating operation, but, multi-separation was introduced in order to illuminate that the multi-separation could do the same work.(2) The vertex coloring problem of graph. This is a classical NP-complete problem. Though there were several DNA algorithms of this problem, the coding methods in these algorithms were complicated, and these algorithms themselves were inefficient. Using the ideal which Lipton solved the SAT problem, we proposed a DNA algorithm based on sticker model. An improved algorithm with separation techniques was given to reduce the operation steps. Finally, the efficiency was improved.(3) The k-coloring problem of map. The four-color theory told us that any map could be colored normally with four kinds of colors. But two or three kinds of colors would do to some specific maps. The map coloring problem was solved in the way of transforming it into the vertex coloring problem of graph.Instances were given to solve the three problems above. And the solutions were got by simulating experiments. So, the feasibility and validity of these algorithms were proved. |
