CaltechAUTHORS
  A Caltech Library Service

On the Computational Power of DNA Annealing and Ligation

Winfree, Erik (1996) On the Computational Power of DNA Annealing and Ligation. In: DNA Based Computers. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. No.27. American Mathematical Society , Providence, RI, pp. 199-221. ISBN 0821805185 http://resolver.caltech.edu/CaltechAUTHORS:20111024-133436564

[img]
Preview
PDF - Submitted Version
See Usage Policy.

296Kb
[img]
Preview
PDF - Published Version
See Usage Policy.

4Mb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111024-133436564

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.


Item Type:Book Section
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.
Funders:
Funding AgencyGrant Number
National Institute for Mental Health (NIMH) Training Grant 5 T32 MH 19138-05
General Motors Technology Research Partnerships ProgramUNSPECIFIED
Record Number:CaltechAUTHORS:20111024-133436564
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20111024-133436564
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27382
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:26 Oct 2011 15:47
Last Modified:26 Dec 2012 14:18

Repository Staff Only: item control page