A Caltech Library Service

Algorithmic Self-Assembly of DNA


Winfree, Erik (1998) Algorithmic Self-Assembly of DNA. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/HBBV-PF79.


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.))
Subject Keywords:Computation and Neural Systems
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:
  • Abu-Mostafa, Yaser S. (chair)
  • Abelson, John N.
  • Adleman, Leonard M.
  • Baldeschwieler, John D.
  • Barr, Alan H.
  • Hopfield, John J.
Defense Date:19 May 1998
Non-Caltech Author Email:winfree (AT)
Funding AgencyGrant Number
NIHT32 MH 19138-07
General Motors Technology ResearchUNSPECIFIED
Japan Society for the Promotion of ScienceJSPS-RFTF 96I00101
Record Number:CaltechETD:etd-05192003-110022
Persistent URL:
Winfree, Erik0000-0002-5899-7523
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:29 Feb 2020 01:54

Thesis Files

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


Repository Staff Only: item control page