Research On Computational Model Of DNA Self-Assembly And Its Application In Graph Coloring Problem

Fast, powerful and universal computational models are the basis of the implementation of DNA Computer. DNA computing by self-assembly has been proved scalable experimentally. Owing to its computational universalism, computing by DNA self-assembly is currently widely studied, and diversified theoretical models have been proposed to solve various NP problems. Because of its autonomy and programmability, DNA self-assembly is deemed to be a feasible mechanism for constructing the DNA chip. Thus, it's significant theoretically and practically to do research on the computational model of DNA self-assembly.The computational capabilities of linear, dendrimer, two deminsional and three dimensional self-assembly are studied. Several theories which have been proved according to the formal language theory are reviewed, including: linear self-assembly is equalient to the regular languages; dendrimer self-assembly is equalient to context-free languages; two dimensional self-assembly is equalient to the Turning-recognizble languages.The main contributions in this paper are as follows:1. A 3D DNA self-assembly computational model is proposed. Firstly, the feasibility of constructing the 3D DNA tile is demonstrated. Secondly, the mathematic theory and formal expression of the 3D self-assembly model is presented based on the 2D tile assembly model. This work is the foundation for further application of the 3D self-assembly model.2. An enumerative 3D DNA self-assembly model for the Graph coloring problem is proposed. Firstly, a non-deterministic algorithm is introduced. Then, different types of DNA tiles are designed according to the algorithm. Lastly, the self-assembling process is demonstrated and the complexity of the model is discussed. As the analysis shows that the self-assembly process is finished in linear time and requires only a constant number of tile types. For the 3-coloring problem, the number of tile types is 20.3. A non-enumerative 3D DNA self-assembly model for the Graph coloring problem is proposed. Firstly, a non-deterministic algorithm with prune stretagy is designed, which can reduce the solution space of the self-assembly model. Then, a tile assembly system is designed to implement the algorithm. Lastly, it's proved theoretically that the tile system can determine arbitrary graph's k-coloring scheme non-deterministically, as long as it's k-colorable. The analysis shows that the number of tile types required in our model is independent to the size of the problem, and the assembling time is linear. For the 3-coloring problem, the number of tile types is 62.