Yaakov Benenson^1,2, Tamar Paz-Elizur¹, Rivka Adar¹, Ehud Keinan³, Zvi Livneh¹ & Ehud Shapiro^1,2
1Department of Biological Chemistry and ²Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
³Department of Chemistry and Institute of Catalysis Science and Technology Technion, Israel Institute of Technology, Haifa 32000, Israel and Department of Molecular Biology and Skaggs Institute of Chemical Biology, The Scripps Research Institute, La Jolla, California 92037, USA

Devices that convert information from one form into another according to a definite procedure are known as automata. One such hypothetical device is the universal Turing machine which stimulated work leading to the development of modern computers. The Turing machine and its special cases including finite automata operate by scanning a data tape, whose striking analogy to information-encoding biopolymers inspired several designs for molecular DNA computers. Laboratory-scale computing using DNA and human-assisted protocols has been demonstrated but the realization of computing devices operating autonomously on the molecular scale remains rare. Here we describe a programmable finite automaton comprising DNA and DNA-manipulating enzymes that solves computational problems autonomously. The automaton's hardware consists of arestriction nuclease and ligase, the software and input are encoded by double-stranded DNA, and programming amounts to choosing appropriate software molecules. Upon mixing solutions containing these components, the automaton processes the input molecule via a cascade of restriction, hybridization and ligation cycles, producing a detectable output molecule that encodes the automaton's final state, and thus the computational result. In our implementation 10¹² automata sharing the same software run independently and in parallel on inputs (which could, in principle, be distinct) in 120 ml solution at room temperature at a combined rate of 10⁹ transitions per second with a transition fidelity greater than 99.8%, consuming less than 10^-10 W.


Nature 414, 430-434 (22 November 2001)