Programmable and autonomous computing machine made of biomolecules

Abstract

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^4,5,6,7,8. Laboratory-scale computing using DNA and human-assisted protocols has been demonstrated^{9,10,11,12,13,14,15}, but the realization of computing devices operating autonomously on the molecular scale remains rare^{16,17,18,19,20}. Here we describe a programmable finite automaton comprising DNA and DNA-manipulating enzymes that solves computational problems autonomously. The automaton's hardware consists of a restriction 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 μl 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.