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.
Although mathematics has long been intertwined with the biological sciences, an explosive synergy between biology and mathematics seems poised to enrich and extend both fields greatly in the coming decades (Levin 1992; Murray 1993; Jungck 1997; Hastings et al. 2003; Palmer et al. 2003; Hastings and Palmer 2003). Biology will increasingly stimulate the creation of qualitatively new realms of mathematics. Why? In biology, ensemble properties emerge at each level of organization from the interactions of heterogeneous biological units at that level and at lower and higher levels of organization (larger and smaller physical scales, faster and slower temporal scales). New mathematics will be required to cope with these ensemble properties and with the heterogeneity of the biological units that compose ensembles at each level.