Algorithmic self-assembly of DNA Sierpinski triangles.
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.
Rothemund
Paul W K
PW
Computation and Neural Systems, California Institute of Technology, Pasadena, USA.
Papadakis
Nick
N
Winfree
Erik
E
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
D004247:DNA