A Caltech Library Service

Algorithmic self-assembly of DNA


Winfree, Erik (1998) Algorithmic self-assembly of DNA. Dissertation (Ph.D.), California Institute of Technology.


How can molecules compute? In his early studies of reversible computation, Bennett imagined an enzymatic Turing Machine which modified a hetero-polymer (such as DNA) to perform computation with asymptotically low energy expenditures. Adleman's recent experimental demonstration of a DNA computation, using an entirely different approach, has led to a wealth of ideas for how to build DNA-based computers in the laboratory, whose energy efficiency, information density, and parallelism may have potential to surpass conventional electronic computers for some purposes. In this thesis, I examine one mechanism used in all designs for DNA-based computer -- the self-assembly of DNA by hybridization and formation of the double helix -- and show that this mechanism alone in theory can perform universal computation. To do so, I borrow an important result in the mathematical theory of tiling: Wang showed how jigsaw-shaped tiles can be designed to simulate the operation of any Turing Machine. I propose constructing molecular Wang tiles using the branched DNA constructions of Seeman, thereby producing self-assembled and algorithmically patterned two-dimensional lattices of DNA. Simulations of plausible self-assembly kinetics suggest that low error rates can be obtained near the melting temperature of the lattice; under these conditions, self-assembly is performing reversible computation with asymptotically low energy expenditures. Thus encouraged, I have begun an experimental investigation of algorithmic self-assembly. A competition experiment suggests that an individual logical step can proceed correctly by self-assembly, while a companion experiment demonstrates that unpatterned two dimensional lattices of DNA will self-assemble and can be visualized. We have reason to hope, therefore, that this experimental system will prove fruitful for investigating issues in the physics of computation by self-assembly. It may also lead to interesting new materials.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computation and Neural Systems
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Hopfield, John J.
Thesis Committee:
  • Unknown, Unknown
Defense Date:19 May 1998
Non-Caltech Author Email:winfree (AT)
Record Number:CaltechETD:etd-05192003-110022
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1866
Deposited By: Imported from ETD-db
Deposited On:19 May 2003
Last Modified:26 Dec 2012 02:43

Thesis Files

PDF (winfree_thesis.pdf) - Final Version
See Usage Policy.

Postscript ( - Final Version
See Usage Policy.


Repository Staff Only: item control page