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

PDF - Submitted Version
See Usage Policy.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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
Winfree, Erik0000-0002-5899-7523
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.
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
Record Number:CaltechAUTHORS:20111024-101156919
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27378
Deposited By: Tony Diaz
Deposited On:26 Oct 2011 15:50
Last Modified:07 Mar 2015 00:27

Repository Staff Only: item control page