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

On the Computational Power of DNA Annealing and Ligation

Abstract

In [20] it was shown that the DNA primitives of Separate, Merge, and Amplify were not sufficiently powerful to invert functions defined by circuits in linear time. Dan Boneh et al [4] show that the addition of a ligation primitive, Append, provides the missing power. The question becomes, "How powerful is ligation? Are Separate, Merge, and Amplify necessary at all?" This paper proposes to informally explore the power of annealing and ligation for DNA computation. We conclude, in fact, that annealing and ligation alone are theoretically capable of universal computation.

Additional Information

© 1996 American Mathematical Society. This work is supported in part by National Institute for Mental Health (NIMH) Training Grant # 5 T32 MH 19138-05; also by General Motors' Technology Research Partnerships program. I would like to thank Paul W. K. Rothemund and Sam Roweis for their stimulating discussion. I am indebted to Ned Seeman for many excellent suggestions, as well as fundamental research on the biochemistry this proposal hopes to exploit; and to Len Adleman for inspiration and great discussions. John Baldeschwieler, Tom Theriault, Marc Unger, Sanjoy Mahajan, Carlos Brody, Dave Kewley, Pam Reinagel, Al Barr, and Stuart Kauffman gave many useful suggestions. Thanks to my advisor John Hopfield for his support and encouragement.

Attached Files

Published - Computational_Power.pdf

Submitted - ligation_preprint.pdf

Files

Computational_Power.pdf
Files (5.2 MB)
Name Size Download all
md5:9ece1cde11cf6eab4fe66a23f8d72f7b
4.9 MB Preview Download
md5:d3341277448173a91943917495d974f6
303.3 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
January 13, 2024