Bio-Molecular Computing of Finite-State Machine

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

We overview a series of our research on implementing finite 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 implement finite automata in test tube. In the length-encoding method, the states and state transition functions of a target finite automaton are effectively encoded into DNA sequences, 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 determined by the detection of a completely hybridized double-strand DNA. Second, We report our intensive in vitro experiments in which we have implemented and executed several 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 mechanism of E. coli. Our fundamental idea to develop a programmable and autonomous finite-state automata on E. coli is that we first encode an input string into one plasmid, encode state-transition functions into the other plasmid, and introduce those two plasmids into an E. coli cell by electroporation. Fourth, we execute a protein-synthesis process in E. coli combined with four-base codon techniques to simulate a computation (accepting) process of finite automata, which has been proposed for in vitro translation-based computations in [4]. This approach enables us to develop a programmable in vivo computer by simply replacing a plasmid encoding a state-transition function with others. Further, our in vivo finite automata are autonomous because the protein-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.

Original languageEnglish
Title of host publication3rd International ICST Conference on Bio-Inspired Models of Network, Information and Computing Systems, BIONETICS 2008
PublisherICST
ISBN (Print)9789639799356
DOIs
Publication statusPublished - 2008
Event3rd International ICST Conference on Bio-Inspired Models of Network, Information and Computing Systems, BIONETICS 2008 - Hyogo, Japan
Duration: 2008 Nov 252008 Nov 28

Publication series

Name3rd International ICST Conference on Bio-Inspired Models of Network, Information and Computing Systems, BIONETICS 2008

Conference

Conference3rd International ICST Conference on Bio-Inspired Models of Network, Information and Computing Systems, BIONETICS 2008
Country/TerritoryJapan
CityHyogo
Period08/11/2508/11/28

Keywords

  • DNA computing
  • finite-state automata
  • molecular computing

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Information Systems
  • Health Informatics

Fingerprint

Dive into the research topics of 'Bio-Molecular Computing of Finite-State Machine'. Together they form a unique fingerprint.

Cite this