Algorithmic Self-Assemblyof DNA Sierpinski TrianglesPaul W. K. Rothemund1,2, Nick Papadakis2, Erik Winfree1,2*1 Computation and Neural Systems, California Institute of Technology, Pasadena, California, United States of America, 2 Computer Science, California Institute ofTechnology, Pasadena, California, United States of AmericaAlgorithms and information, fundamental to technological and biological organization, are also an essential aspect ofmany 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 binaryfunction XOR and thus fabricates a fractal pattern—a Sierpinski triangle—as it grows. To achieve this, abstract tileswere 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 independentmolecular realizations, atomic force microscopy revealed recognizable Sierpinski triangles containing 100–200 correcttiles. Error rates during assembly appear to range from 1% to 10%. Although imperfect, the growth of Sierpinskitriangles 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 ofimplementing any desired algorithm for computation or construction tasks.Citation: Rothemund PWK, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2(12): e424.IntroductionHow is complex organization produced and maintained byphysical processes? One may look to biology, where we findthe most sophisticated organization of matter, often spanningmore than 24 orders of magnitude from componentmolecules (0.1 attograms) to entire organism (100 kilograms).This organization is information-based: DNA sequencesrefined by evolution encode both the components and theprocesses that guide their development into an organism—the developmental program. For a language to describe thiscarefully orchestrated organization, it is tempting to turn tocomputer science, where the concepts of programminglanguages, data structures, and algorithms are used to specifycomplex organization of information and behavior. Indeed,the importance of universal computation for autonomousfabrication tasks was recognized in von Neumann’s seminalwork on self-reproducing automata, where he postulated auniversal constructor that, by reading an input tape specifyingan algorithm for what to build, could carry out the commandsnecessary to construct an arbitrary object (von Neumann1966). If algorithmic concepts can be successfully adapted tothe molecular context, the algorithm would join energy andentropy as essential concepts for understanding how physicalprocesses create order. Unfortunately, the study of molecularalgorithms has been hampered by the lack of suitable physicalsystems on which to hone such a theory: nature provides uswith elementary chemical reactions too simple to program,full-blown life too complex to use as a model system, and fewsystems in between. This gap may be explored by synthesizingprogrammable biochemical systems in vitro, where we canimplement and study a variety of molecular algorithmsranging gradually from simple to complex.Biomolecular self-assembly is particularly attractive for theexploration of molecular algorithms that control nanofabri-cation tasks. Attesting to its power, self-assembly is usedpervasively in biology to create such structures as virus capsids,microtubules, and flagella. In each case, the binding inter-actions between a small number of protein species is sufficientto dictate the form of the final structure, often via a complexsequence of cooperative assembly steps. This can be viewedloosely as a form of programmable nanofabrication, where theprogram is the set of molecular species involved. For syntheticapproaches, Seeman (1982, 2003) has demonstrated that DNAprovides an alternative to p rotein that can be readilyprogrammed by Watson–Crick complementarity. A seminalpaper by Adleman (1994) used one-dimensional (1D) DNA self-assembly to operate as a finite-state machine, establishing thefirst experimental connection between DNA self-assembly andcomputation. This work inspired a theoretical pr oposal(Winfree 1996) that builds on Wang’s (1961, 1962) embeddingof computation in geometrical tilings to show that two-dimensional (2D) self-assembly of DNA can perform Turing-universal computation—which implies that any algorithm canin principle be embedded in, and guide, a potentiallyaperiodic crystallization process. In this ‘‘algorithmic self-assembly’’ paradigm, a set of molecular Wang tiles is viewed asthe program for a particular computation or molecularfabrication task (Reif 1999; Rothemund and Winfree 2000;Received September 14, 2004; Accepted October 5, 2004; Published December7, 2004DOI: 10.1371/journal.pbio.0020424Copyright: Ó 2004 Rothemund et al.This is an open-access article distributedunder the terms of the Creative Comm ons Attribution License, which permitsunrestricted use, distribution, and reproduction in any medium, provided theoriginal work is properly cited.Abbreviations: 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 intermolecularspacing; DAO-E, double-cros sover, antiparallel, odd intramolecular spacing, evenintermolecular spacing; kTAM, kinetic Tile Assembly Model; PCR, polymerase chainreaction; RAM, random-access memory; XOR, exclusive orAcademic Editor: Anne Condon, University of British Columbia*To whom correspondence should be address ed. E-mail:[email protected] Biology | www.plosbiology.org December 2004 | Volume 2 | Issue 12 | e4242041Open access, freely available onlinePLoSBIOLOGYAdleman et al. 2001). (This framework differs from previousapproaches relating tiling theory to crystalline ground-states[Radin 1985] in that kinetic phenomena are essential here.)Whereas 1D algorithmic self-assembly offers limited computa-tional power (Winfree et al. 1998b) and has been experimen-tally demonstrated (Adleman 1994; Mao et al. 2000), 2Dalgorithmic self-assembly offers not only new