Bio-Molecular Computing of Finite-State Machine

We overview a series of our research on implementing fi- nite automata in vitro and in vivo in the framework of DNA-based computing [2, 3]. First, we employ the length- encoding technique proposed and presented in [5, 4] to im- plement finite automata in test tube. In the length-encoding method, the states and state transition functions of a tar- get finite automaton are effectively encoded into DNA se- quences, a computation (accepting) process of finite automata is accomplished by self-assembly of encoded complementary DNA strands, and the acceptance of an input string is deter- mined by the detection of a completely hybridized double- strand DNA. Second, We report our intensive in vitro ex- periments in which we have implemented and executed sev- eral finite-state automata in test tube. We have designed and developed practical laboratory protocols which combine several in vitro operations such as annealing, ligation, PCR, and streptavidin-biotin bonding to execute in vitro finite automata based on the length-encoding technique. We have carried laboratory experiments on various finite automata of from 2 states to 6 states for several input strings. Third, we present a novel framework to develop a programmable and autonomous in vivo computer using Escherichia coli (E. coli), and implement in vivo finite-state automata based on the framework by employing the protein-synthesis mech- anism of E. coli. Our fundamental idea to develop a pro- grammable and autonomous finite-state automata on E. coli is that we first encode an input string into one plasmid, en- code state-transition functions into the other plasmid, and introduce those two plasmids into an E. coli cell by electro- poration. Fourth, we execute a protein-synthesis process in E. coli combined with four-base codon techniques to simu- late a computation (accepting) process of finite automata, which has been proposed for in vitro translation-based com- putations in [4]. This approach enables us to develop a pro- grammable in vivo computer by simply replacing a plasmid encoding a state-transition function with others. Further, our in vivo finite automata are autonomous because theprotein-synthesis process is autonomously executed in the living E. coli cell. We show some successful experiments to run an in vivo finite-state automaton on E. coli.