Intensive in vitro experiments of implementing and executing finite automata in test tube

Junna Kuramochi, Yasubumi Sakakibara

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

5 Citations (Scopus)


We report our intensive in vitro experiments in which we have implemented and executed several finite-state automata in test tube. First, we employ the length-encoding technique proposed and presented in [4, 3] 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 design and develop 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. To our knowledge, this is the first in vitro experiments that have succeeded to execute 6-states automaton in test tube.

Original languageEnglish
Title of host publicationDNA Computing - 11th International Workshop on DNA Computing, DNA11, Revised Selected Papers
Number of pages10
Publication statusPublished - 2006 Jul 13
Event11th International Workshop on DNA Computing, DNA11 - London, ON, Canada
Duration: 2005 Jun 62005 Jun 9

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3892 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other11th International Workshop on DNA Computing, DNA11
CityLondon, ON

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Intensive in vitro experiments of implementing and executing finite automata in test tube'. Together they form a unique fingerprint.

Cite this