DNA Self-Assembly Realization Of Molecular Cellular Automata

In 1994, professor Adleman in Southern California University in USA solved the Directed Hamilton Path Problem successfully by operating the DNA molecules in solution, which indicating the beginning of biological computing era. In 1995, Winfree proposed an important idea that the self-assembly of DNA molecular tiles could be used to implement computation;and with his work, he established the academic and experimental foundation solidly for the development of the DNA computing.The Cellular Automaton is a kind of Discrete Dynamical Systems proposed by Stanislaw M. Ulam and John von Neumann in 1950's. It is the initial theory framework for the research of complex system, and also the embryonic form of the artificial intelligence. Some kinds of DNA self-assembly methods for realizing one-dimensional molecular cellular automata has been proposed in recent years, but no one ideal model of the two-dimensional molecular cellular automata realized by using DNA self-assembly method has been proposed hitherto, this article will do some exploring research in this aspect, and present two theory model of the two-dimensional molecular cellular automata realized via DNA self-assembly.In this article, at first,I will review the DNA self-assembly realization methods of the one-dimensional cellular automata introduced by Rothemund and Yin Peng et al respectively, then I will analyze the possibility and the complexity degree of realizing the two-dimensional cellular automata by the self-assembly of four-arm DNA molecular tiles, and get the conclusion that we could realize the two- dimensional cellular automata using the self-assembly of four-arm DNA molecular tiles, but the process of the assembly is a little complex.Then, in this article, I will introduce two methods for realizing the two-dimensional molecular cellular automata respectively: one is by self-assembly of eight-arm string shape DNA molecular tiles, and another is by self-assembly of six-arm TX molecular tiles, which has the recognition site of protein enzymes on four of its arms. In the latter method for realizing two-dimensional molecular cellular automata, I creatively solved the problem about information transmitting, which was a difficult problem in the DNA computing research field. In the progress of realizing the two-dimensional molecular cellular automata, the information transmitting problem is, when the state of cellular space is changing, how to transmit the state information of the neighbors to current cell and how to transmit the state information of this time to next time, and so on. In my work, I introduced an excellent method to solve the information transmitting problem, which examined the information by molecular automata and revised the information by transforming molecules.Finally, in this article, I will discusse the application of the two-dimensional molecular cellular automata in simulating complex systems, including the simulation of"the self-duplicating cellular automata"and"the life game". These two kinds of cellular automata both have the computation ability of Turing universal machine. From the results of electronic computer simulation, we can see the two-dimensional molecular cellular automata could realize these computations definitely.Based on the theory about relation between automata and the Chomsky language family, in fact, I have constructed a new model of molecular computer - the two-dimensional cellular automata with two approaches in this article, which could implement Turing universal computation. The two-dimensional cellular automata have been applied wildly in many fields, especially the simulation and research about complex system, and considering the development of biochemistry technology and the demand for solving more and more complex computation problems, we can believe, in the future not far from now, the molecular cellular automata realized by DNA self-assembly on the molecular level will bring valuable fortune for our society and economy.