title: Algorithmic self-assembly of DNA Sierpinski triangles.
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.
authors.affiliation: Computation and Neural Systems, California Institute of Technology, Pasadena, USA.
authors.forename: Paul W K
authors.initials: PW
authors.lastname: Rothemund
authors.forename: Nick
authors.initials: N
authors.lastname: Papadakis
authors.forename: Erik
authors.initials: E
authors.lastname: Winfree
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D001703:Biophysics / Q000379:methods; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D039301:Computers, Molecular; D004247:DNA / Q000737:chemistry*; D005818:Genetic Engineering; D018625:Microscopy, Atomic Force; D008957:Models, Genetic; D015203:Reproducibility of Results; D017422:Sequence Analysis, DNA; D014466:Ultraviolet Rays
chemical_list: D004247:DNA