DNA molecule provides a computing machine withboth data and fuelYaakov Benenson*†‡, Rivka Adar†‡, Tamar Paz-Elizur†, Zvi Livneh†, and Ehud Shapiro*†§Departments of *Computer Science and Applied Mathematics and†Biological Chemistry, Weizmann Institute of Science, Rehovot 76100, IsraelEdited by Peter B. Dervan, California Institute of Technology, Pasadena, CA, and approved January 13, 2003 (received for review September 17, 2002)The unique properties of DNA make it a fundamental buildingblock in the fields of supramolecular chemistry, nanotechnology,nano-circuits, molecular switches, molecular devices, and molecu-lar computing. In our recently introduced autonomous molecularautomaton, DNA molecules serve as input, output, and software,and the hardware consists of DNA restriction and ligation enzymesusing ATP as fuel. In addition to information, DNA stores energy,available on hybridization of complementary strands or hydrolysisof its phosphodiester backbone. Here we show that a single DNAmolecule can provide both the input data and all of the necessaryfuel for a molecular automaton. Each computational step of theautomaton consists of a reversible software molecule兾input mol-ecule hybridization followed by an irreversible software-directedcleavage of the input molecule, which drives the computationforward by increasing entropy and releasing heat. The cleavageuses a hitherto unknown capability of the restriction enzyme FokI,which serves as the hardware, to operate on a noncovalentsoftware兾input hybrid. In the previous automaton, software兾inputligation consumed one software molecule and two ATP moleculesper step. As ligation is not performed in this automaton, a fixedamount of software and hardware molecules can, in principle,process any input molecule of any length without external energysupply. Our experiments demonstrate 3 ⴛ 1012automata per␮lperforming 6.6 ⴛ 1010transitions per second per␮l with transitionfidelity of 99.9%, dissipating about 5 ⴛ 10ⴚ9W兾␮l as heat atambient temperature.The function of DNA is to store hereditary information andregulate the expression of this information (1). The uniquechemical properties of DNA encouraged its utilization in novelcontexts. The highly selective base pairing renders DNA anexcellent building block for supramolecular ensembles, one ofthe few that can assemble in an aqueous environment. DNA mayserve either as a principal structural component or as a mediatorthat arranges tethered ligands or particles (2, 3). The formerapproach encompasses nanoscale DNA constructs (4) and ex-tended spatial structures (5). The latter includes DNA-directedassembly of proteins (6), fullerenes (7), and golden particles (8)and DNA-templated nanowire formation (9). DNA also formsdynamic constructs, such as a molecular switch (10) and oscil-lating molecular machines (11, 12). DNA recognition propertiesare also exploited in antisense regulation of gene expression (13).The combination of information-encoding and recognitioncapabilities of DNA, and the enzymatic machinery available forDNA manipulation, facilitated the emergence of the field ofbiomolecular computing. Experimental DNA computers (14–23) use single-stranded or double-stranded DNA to encode theirdata and possibly the software. These molecules interact in aprogrammed fashion, accompanied by enzymatic or manualmanipulations, providing a DNA molecule encoding an output.So far, little attention has been given to the energetic aspectsof DNA computers. In practice, all of the protocols use ATP toallow ligation and兾or heating to allow strand dissociation. How-ever, the reverse operations, i.e., the hydrolysis of the DNAbackbone and strand hybridization, are spontaneous becausethey are driven by the potential free energy stored in DNA itself.A molecular computer using these operations may, in principle,be fueled by its DNA input. In fact, the potential free energy ofsingle-stranded DNA was used in noncomputational context tofuel oscillating devices (11, 12). Here we describe a DNA-basedfinite automaton that computes via repeated cycles of self-assembly and processing. The reversible self-assembly is drivenby hybridization energy between input兾software complementarysticky ends, whereas the irreversible processing step is drivenexclusively by the energy released upon hydrolysis of the inputDNA backbone and does not require ATP or heating. Ourautomaton can, in principle, use a fixed amount of software andhardware molecules to process any input molecule of any lengthwithout external energy supply, and as such provides experi-mental realization of the theoretical possibility to use thepotential energy of a DNA input molecule to drive a molecularcomputation.Materials and MethodsMaterials. FokI stock (54␮M, 60 units兾␮l), T4 DNA ligase (400units兾␮l), and T4 polynucleotide kinase (PNK) (10 units兾␮l)were from New England Biolabs. Redivue [␥-32P]ATP (⬇3,000mCi兾mmol, 3.33 pmol兾␮l) and ATP (100 mM) were obtainedfrom Amersham Pharmacia. Synthetic oligonucleotides (de-salted and lyophilized, 1-␮mol scale) were from Sigma-Genosys.Assembly of the Machine Components. Single-stranded componentsof the software and inputs were purified to homogeneity by usinga 15% denaturing acrylamide gel (40 cm ⫻ 1.5 mm) containing8 M urea (24). The oligonucleotides for the construction of thesoftware were TN1368 (5⬘-AAGAGCTAGAGTCGGATGC),TN24 (5⬘-AAGAGCTAGAGTCGGATGCC), TN57 (5⬘-AAGAGCTAGAGTCGGATG), TN1-as (5⬘-AGCCGCATC-CGACTCTAGCTCT), TN2-as (5⬘-AGCCGGCATCCG-ACTCTAGCTCT), TN3-as (5⬘-CCTGGCATCCGACTC-TAGCTCT), TN4-as (5⬘-CCTGGGCATCCGACTCTAG-CTCT), TN5-as (5⬘-GCCACATCCGACTCTAGCTCT),TN6-as (5⬘-GCCAGCATCCGACTCTAGCTCT), TN7-as (5⬘-CTGCCATCCGACTCTAGCTCT), and TN8-as (5⬘-CTGCG-CATCCGACTCTAGCTCT).The software molecules were prepared by annealing thefollowing pairs of oligonucleotides: T1, TN1368 and TN1-as; T2,TN24 and TN2-as; T3, T1368 and TN3-as; T4, TN24 and TN4-as;T5, TN57 and TN5-as; T6, TN1368 and TN6-as; T7, TN57 andTN7-as; and T8, TN1368 and TN8-as.The oligonucleotides for the construction of the inputs were:abb-s (5⬘-GGCTGCCGCAGGGCCGCAGGGCCGTCGG-TACCGATTAAGTTGGA), abb-as (5⬘-CCAACTTAATCGG-TACCGACGGCCCTGCGGCCCTGCGGC), abba-s (5⬘-G-GCTGCCGCAGGGCCGCAGGGCCTGGCTGCCGTCGG-TACCGATTAAGTTGGA), abba-as (5⬘-CCAACTTAATCG-GTACCGACGGCAGCCAGGCCCTGCGGCCCTGCGGC),babb2-s (5⬘-CAGGGCCTGGCTGCCGCAGGGCCGCA-This paper was submitted directly (Track II) to the PNAS