Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 1996 | Submitted + Published
Book Section - Chapter Open

A DNA and restriction enzyme implementation of Turing Machines


Bacteria employ restriction enzymes to cut or restrict DNA at or near specific words in a unique way. Many restriction enzymes cut the two strands of double-stranded DNA at different positions leaving overhangs of single-stranded DNA. Two pieces of DNA may be rejoined or ligated if their terminal overhangs are complementary. Using these operations fragments of DNA, or oligonucleotides, may be inserted and deleted from a circular piece of plasmid DNA. We propose an encoding for the transition table of a Turing machine in DNA oligonucleotides and a corresponding series of restrictions and ligations of those oligonucleotides that, when performed on circular DNA encoding an instantaneous description of a Turing machine, simulate the operation of the Turing machine encoded in those oligonucleotides. DNA based Turing machines have been proposed by Charles Bennett but they invoke imaginary enzymes to perform the state-symbol transitions. Our approach differs in that every operation can be performed using commercially available restriction enzymes and ligases.

Additional Information

© 1996 American Mathematical Society. I would like to thank Max and Judith Rothemund for the generous grant that made my studies at the California Institute of Technology possible. Yaser Abu-Mostafa (dept of electrical engineering California of Technology) provided great enthusiasm, encouragement, and input for what was an unusual project. Erik Winfree (CNS Caltech) has kept me working and without him, I never would have attended DIMACS. I would like to thank Kai Zinn (dept of Biology California Institute of Technology) for letting me use DNA Strider early on; Greg Fu (dept of chemistry Massachusetts Institute of Technology) and Randy Lee (dept of Chemistry University of Houston) for encouraging my interest in chemistry; Sam Roweis and Len Adleman for their stimulating discussion; Nadrian Seeman for discussion on error correction; and Aditi Dhagat, Barun Chandra, and Amitabh Shah for introducing me to CS. Finally, I would like to dedicate this paper to the late J .L.A. van de Snepscheut, (Dept of Computer Science California Institute of Technology) for introducing me to the idea of a DNA Turing machine [34]. He would have been excited and pleased by the development of DNA computation.

Attached Files

Published - DNA_Restriction.pdf

Submitted - dimacs_preprint.pdf


Files (9.7 MB)
Name Size Download all
9.4 MB Preview Download
318.6 kB Preview Download

Additional details

August 22, 2023
January 13, 2024