Interesting Esoterica

Algorithmic self-assembly of DNA Sierpinski triangles.

Article by Rothemund, Paul W K and Papadakis, Nick and Winfree, Erik
  • Published in 2004
  • Added on
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.

Links

Other information

issn
1545-7885
journal
PLoS biology
keywords
Algorithms,Base Sequence,Biophysics,Biophysics: methods,Computational Biology,Computational Biology: methods,Computer Simulation,Computers, Molecular,DNA,DNA: chemistry,Genetic Engineering,Microscopy, Atomic Force,Models, Genetic,Reproducibility of Results,Sequence Analysis, DNA,Ultraviolet Rays
number
12
pages
e424
publisher
Public Library of Science
volume
2

BibTeX entry

@article{Rothemund2004,
	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.},
	author = {Rothemund, Paul W K and Papadakis, Nick and Winfree, Erik},
	issn = {1545-7885},
	journal = {PLoS biology},
	keywords = {Algorithms,Base Sequence,Biophysics,Biophysics: methods,Computational Biology,Computational Biology: methods,Computer Simulation,Computers, Molecular,DNA,DNA: chemistry,Genetic Engineering,Microscopy, Atomic Force,Models, Genetic,Reproducibility of Results,Sequence Analysis, DNA,Ultraviolet Rays},
	month = {dec},
	number = 12,
	pages = {e424},
	publisher = {Public Library of Science},
	title = {Algorithmic self-assembly of DNA Sierpinski triangles.},
	url = {http://dx.plos.org/10.1371/journal.pbio.0020424},
	volume = 2,
	year = 2004,
	urldate = {2013-01-18}
}