CaltechAUTHORS
  A Caltech Library Service

Algorithmic Self-Assembly of DNA Sierpinski Triangles

Rothemund, Paul W. K. and Papadakis, Nick and Winfree, Erik (2004) Algorithmic Self-Assembly of DNA Sierpinski Triangles. PLoS Biology, 2 (12). pp. 2041-2053. ISSN 1544-9173. http://resolver.caltech.edu/CaltechAUTHORS:ROTpb04

[img]
Preview
PDF - Published Version
Creative Commons Attribution.

4Mb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:ROTpb04

Abstract

Algorithms and information, fundamental to technological and biological organization, are also an essential aspect of many elementary physical phenomena, such as molecular self-assembly. Here we report the molecular realization, using two-dimensional self-assembly of DNA tiles, of a cellular automaton whose update rule computes the binary function XOR and thus fabricates a fractal pattern — a Sierpinski triangle — as it grows. To achieve this, abstract tiles were translated into DNA tiles based on double-crossover motifs. Serving as input for the computation, long single-stranded DNA molecules were used to nucleate growth of tiles into algorithmic crystals. For both of two independent molecular realizations, atomic force microscopy revealed recognizable Sierpinski triangles containing 100–200 correct tiles. Error rates during assembly appear to range from 1% to 10%. Although imperfect, the growth of Sierpinski triangles demonstrates all the necessary mechanisms for the molecular implementation of arbitrary cellular automata. This shows that engineered DNA self-assembly can be treated as a Turing-universal biomolecular system, capable of implementing any desired algorithm for computation or construction tasks.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1371/journal.pbio.0020424 DOIArticle
http://www.plosbiology.org/article/info:doi/10.1371/journal.pbio.0020424PublisherArticle
Additional Information:© 2004 Rothemund et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Received September 14, 2004; Accepted October 5, 2004; Published December 7, 2004. For discussions, insights, and advice, we thank John Hopfield, Ned Seeman, Len Adleman, Matt Cook, Hui Wang, Rebecca Schulman, Shaun Lee, Rizal Hariadi, and Jason Rolfe. Experiments described in Figure S18 were performed by Jason Rolfe. We thank the Caltech Molecular Materials Research Center for use of their AFM scanners. PWKR was supported by a Beckman Fellowship. This work was supported in part by the National Science Foundation PECASE EIA-0093486, DARPA BioComputation F30602-01-2-0561, NASA NRA2-37143, and GenTel Corporation. Conflicts of interest: The authors have declared that no conflicts of interest exist. Author contributions: PWKR and EW conceived and designed the experiments. PWKR, NP, and EW performed the experiments. PWKR and EW analyzed the data. PWKR and EW wrote the paper.
Funders:
Funding AgencyGrant Number
NSFPECASE EIA-0093486
DARPA BioComputationF30602-01-2-0561
NASANRA2-37143
GenTel CorporationUNSPECIFIED
Subject Keywords:AFM, atomic force microscopy; aTAM, abstract Tile Assembly Model; 1D, one-dimensional; 2D, two-dimensional; DNA, deoxyribonucleic acid; DAE-E, double-crossover, antiparallel, even intramolecular spacing, even intermolecular spacing; DAO-E, double-crossover, antiparallel, odd intramolecular spacing, even intermolecular spacing; kTAM, kinetic Tile Assembly Model; PCR, polymerase chain reaction; RAM, random-access memory; XOR, exclusive or
Record Number:CaltechAUTHORS:ROTpb04
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:ROTpb04
Alternative URL:http://dx.doi.org/10.1371/journal.pbio.0020424
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:290
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:18 May 2005
Last Modified:22 Jun 2014 04:38

Repository Staff Only: item control page