CaltechAUTHORS
  A Caltech Library Service

Universal Computation via Self-assembly of DNA: Some Theory and Experiments

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

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

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

5Mb

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

Abstract

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.
Funders:
Funding AgencyGrant Number
National Institute for Mental Health (NIMH) Training Grant5 T32 MH 19138-06
General Motors Technology Research Partnerships ProgramUNSPECIFIED
NSF Center for Neuromorphic Systems Engineering EEC-9402726
Office of Naval Research (ONR)N00014-89-J-3078
NIHGM-29554
Record Number:CaltechAUTHORS:20111024-101156919
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20111024-101156919
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27378
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:26 Oct 2011 15:50
Last Modified:26 Dec 2012 14:18

Repository Staff Only: item control page