Several DNA Computing Models And Their Actualization

In 1994, Adleman solved a seven vertices Hamiltonian path problem with DNA molecules, which has initiated an emerging research field"DNA computing", which, equipped with modern molecular biology techniques, aims to solve hard computing problem and constructing computing devices with DNA. Due to the intrinsic parallel nature of DNA computing, DNA information storage and its eligibility of in vivo operation, it is believed that DNA computing could potentially overcome the disadvantage of electronic computer and would enable some special application.This paper presents the studies in the fields of DNA finite state automata and DNA addition. Theoretical computation model are proposed together with experimental technique improvements. This paper is composed of the following four parts. Part 1 describes the background of DNA computing. Firstly, some common molecular biological technologies used in DNA computing are introduced. Then, several NP-complete problems are used as examples of how to manipulate DNA molecules to compute. Finally, the development of DNA computing in the past ten years is briefly reviewed.Part 2 describes the research on DNA finite state automata. Constructing Turing machine with DNA molecule is an important branch of DNA computing, because Turing machine is a theoretical universal computing model. The finite state automaton is a type of programmable and autonomous computing device which possess partial Turing machine computing power. We make some technical improvements based on the Benenson DNA finite automata model. First, fluorescence is proposed to be labeled on the 5' end of input molecule, which makes all DNA computing intermediates easily detectable by capillary electrophoresis and result in a convenient data collection for reaction optimization. Second, DNA finite automata reaction is achieved on solid surface. Surface reaction facilitates the combination of DNA computing and automation technology. This study provides technical support to further optimization and development of DNA automata model.Part 3 interprets the study of DNA addition. As a basic computational module of computer, a number of DNA addition algorithms have been proposed in the literature. Two new kinds of DNA addition algorithms are proposed in this chapter. The first one is a parallel addition algorithm, which can achieve continuous carry operation with a unified form to represent input and output strands. Owing to the complicated experimental procedure, only one bit binary addition is accomplished experimentally. The second addition algorithm is based on DNA self-assembly method, whose advantage lies in spontaneous computing process and constant complexity (in terms of steps of experimental procedures), which requires constant experimental steps, rather than growing with n for the addition of two binary n-bit integers. The simplicity of self-assembly addition is demonstrated by several arbitrary four-bit binary additions experiments. A DNA adder proto type is experimentally constructed by combining self-assembly addition algorithm with MEMS technology. The computing component of the adder is made of DNA molecule,and an electronic computer controls the micro pump array, micro fluid mixture chip magnetic reactor and electrochemical DNA sensor to fulfill the experiment procedure of the self-assembly addition algorithm, respectively. This is a step forward to combine DNA computing with MEMS technology.Part 4 summarizes the research discussed in this paper and provides some discussions on the perspective of the DNA computing.