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. https://resolver.caltech.edu/CaltechAUTHORS:20111024-133436564
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Submitted Version
See Usage Policy. 303kB | |
|
PDF
- Published Version
See Usage Policy. 4MB |
Use this Persistent URL to link to this item: https://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 | ||||||
|---|---|---|---|---|---|---|---|
| ORCID: |
| ||||||
| 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: |
| ||||||
| Series Name: | DIMACS Series in Discrete Mathematics and Theoretical Computer Science | ||||||
| Issue or Number: | 27 | ||||||
| Record Number: | CaltechAUTHORS:20111024-133436564 | ||||||
| Persistent URL: | https://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: | 03 Oct 2019 03:23 |
Repository Staff Only: item control page
