Winfree, Erik and Yang, Xiaoping and Seeman, Nadrian C. (1999) Universal Computation via Self-assembly of DNA: Some Theory and Experiments. In: DNA Based Computers II. DIMACS series in discrete mathematics and theoretical computer science. No.44. American Mathematical Society , Providence, RI, pp. 191-213. ISBN 0821807560 http://resolver.caltech.edu/CaltechAUTHORS:20111024-101156919
- Submitted Version
See Usage Policy.
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111024-101156919
In this paper we examine the computational capabilities inherent in the hybridization of DNA molecules. First we consider theoretical models, and show that the self-assembly of oligonucleotides into linear duplex DNA can only generate sets of sequences equivalent to regular languages. If branched DNA is used for self-assembly of dendrimer structures, only sets of sequences equivalent to context-free languages can be achieved. In contrast, the self-assembly of double crossover molecules into two dimensional sheets or three dimensional solids is theoretically capable of universal computation. The proof relies on a very direct simulation of a universal class of cellular automata. In the second part of this paper, we present results from preliminary experiments which investigate the critical computational step in a two-dimensional self-assembly process.
|Item Type:||Book Section|
|Additional Information:||© 1999 American Mathematical Society. E. Winfree has been supported in part by National Institute for Mental Health (NIMH) Training Grant # 5 T32 MH 19138-06; also by General Motors' Technology Research Partnerships program and by the Center for Neuromorphic Systems Engineering as a part of the National Science Foundation Engineering Research Center Program under grant EEC-9402726. The experimental portion of this research has been partially supported by grants N00014-89-J-3078 from the Office of Naval Research and GM-29554 from the NIH (to NCS). Erik Winfree is grateful to the many people who have helped make his foray into the world of molecules possible, enjoyable, and exciting; special thanks go to Len Adleman, Paul Rothemund, Sam Roweis, Dan Abrahams-Gessel, John Hopfield, and John Abelson who generously provided laboratory facilities at Caltech for some of the experiments reported here.|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Tony Diaz|
|Deposited On:||26 Oct 2011 15:50|
|Last Modified:||26 Dec 2012 14:18|
Repository Staff Only: item control page