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 - Published Version
See Usage Policy.

PDF - Submitted 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
Seeman, Nadrian C.0000-0002-9680-4649
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
NIH Predoctoral Fellowship5 T32 MH 19138-06
General Motors Technology Research Partnerships ProgramUNSPECIFIED
Office of Naval Research (ONR)N00014-89-J-3078
Series Name:DIMACS series in discrete mathematics and theoretical computer science
Issue or Number:44
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:09 Mar 2020 13:19

Repository Staff Only: item control page