Programmable and autonomous computing machine made of biomolecules

Devices that convert information from one form into another according to a definite procedure are known as automata. One such hypothetical device is t he universal Turing machine(1), which stimulated work leading to the develo pment of modern computers. The Turing machine and its special cases(2), inc luding finite automata(3), operate by scanning a data tape, whose striking analogy to information-encoding biopolymers inspired several designs for mo lecular DNA computers(4-8). Laboratory-scale computing using DNA and human- assisted protocols has been demonstrated(9-15), but the realization of comp uting devices operating autonomously on the molecular scale remains rare(16 -20). Here we describe a programmable finite automaton comprising DNA and D NA-manipulating enzymes that solves computational problems autonomously. Th e automaton's hardware consists of a restriction nuclease and ligase, the s oftware and input are encoded by double-stranded DNA, and programming amoun ts to choosing appropriate software molecules. Upon mixing solutions contai ning these components, the automaton processes the input molecule via a cas cade of restriction, hybridization and ligation cycles, producing a detecta ble output molecule that encodes the automaton's final state, and thus the computational result. In our implementation 10(12) automata sharing the sam e software run independently and in parallel on inputs (which could, in pri nciple, be distinct) in 120 mul solution at room temperature at a combined rate of 10(9) transitions per second with a transition fidelity greater tha n 99.8%, consuming less than 10(-10) W.