Algorithmic self-assembly of DNA Sierpinski triangles.

• Published in 2004
• Added on 2013-01-18

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

• http://dx.plos.org/10.1371/journal.pbio.0020424

Other information

BibTeX entry

@article{Rothemund2004,
	key = {Rothemund2004},
	type = {article},
	title = {Algorithmic self-assembly of DNA Sierpinski triangles.},
	author = {Rothemund, Paul W K and Papadakis, Nick and Winfree, Erik},
	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.},
	comment = {},
	date_added = {2013-01-18},
	date_published = {2004-12-01},
	urls = {http://dx.plos.org/10.1371/journal.pbio.0020424},
	collections = {},
	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},
	url = {http://dx.plos.org/10.1371/journal.pbio.0020424},
	volume = 2,
	year = 2004,
	urldate = {2013-01-18}
}