In a demonstration that holds promise for future advances
in nanotechnology, California Institute of Technology computer
scientists have succeeded in building a DNA crystal that
computes as it grows. As the computation proceeds, it creates
a triangular fractal pattern in the DNA crystal.
This is the first time that a computation has been embedded
in the growth of any crystal, and the first time that
computation has been used to create a complex microscopic
pattern. And, the researchers say, it is one step in the dream
of nanoscientists to master construction techniques at the
Reporting in the December issue of the journal Public Library of
Science (PLoS) Biology, Caltech assistant professor Erik
Winfree and his colleagues show that DNA "tiles" can be
programmed to assemble themselves into a crystal bearing a
pattern of progressively smaller "triangles within triangles,"
known as a Sierpinski triangle. This fractal pattern is more
complex than patterns found in natural crystals because it
never repeats. Natural crystals, by contrast, all bear
repeating patterns like those commonly found in the tiling of
a bathroom floor. And, because each DNA tile is a tiny knot of
DNA with just 150 base pairs (an entire human genome has some
3 billion), the resulting Sierpinski triangles are
microscopic. The Winfree team reports growing micron-size DNA
crystals (about a hundredth the width of a human hair) that
contain numerous Sierpinski triangles.
A key feature of the Caltech team's approach is that the
DNA tiles assemble into a crystal spontaneously. Comprising a
knot of four DNA strands, each DNA tile has four loose ends
known as "sticky ends." These sticky ends are what binds one
DNA tile to another. A sticky end with a particular DNA
sequence can be thought of as a special type of glue, one that
only binds to a sticky end with a complementary DNA sequence,
a special "anti-glue''. For their experiments, the authors
just mixed the DNA tiles into salt water and let the sticky
ends do the work, self-assembling the tiles into a Sierpinski
triangle. In nanotechnology this "hands off" approach to
manufacturing is a desirable property, and a common theme.
The novel aspect of the research is the translation of an
algorithm--the basic method underlying a computer
program--into the process of crystal growth. A well-known
algorithm for drawing a Sierpinski triangle starts with a
sequence of 0s and 1s. It redraws the sequence over and over
again, filling up successive rows on a piece of paper, each
time performing binary addition on adjacent digits.
The result is a Sierpinski triangle built out of 0s and 1s.
To embed this algorithm in crystal growth, the scientists
represented written rows of binary "0s" and "1s" as rows of
DNA tiles in the crystal--some tiles stood for 0, and others
for 1. To emulate addition, the sticky ends were designed to
ensure that whenever a free tile stuck to tiles already in the
crystal, it represented the sum of the tiles it was sticking
The process was not without error, however. Sometimes DNA
tiles stuck in the wrong place, computing the wrong sum, and
destroying the pattern. The largest perfect Sierpinski
triangle that grew contained only about 200 DNA tiles. But it
is the first time any such thing has been done and the
researchers believe they can reduce errors in the future.
In fact the work is the first experimental demonstration of
a theoretical concept that Winfree has been developing since
1995--his proposal that any algorithm can be embedded in the
growth of a crystal. This concept, according to Winfree's
coauthor and Caltech research fellow Paul W. K. Rothemund, has
inspired an entirely new research field, "algorithmic
self-assembly," in which scientists study the implications of
embedding computation into crystal growth.
"A growing group of researchers has proposed a series of
ever more complicated computations and patterns for these
crystals, but until now it was unclear that even the most
basic of computations and patterns could be achieved
experimentally," Rothemund says.
Whether larger, more complicated computations and patterns
can be created depends on whether Winfree's team can reduce
the errors. Whether the crystals will be useful in
nanotechnology may depend on whether the patterns can be
turned into electronic devices and circuits, a possibility
being explored at other universities including Duke and
Nanotechnology applications aside, the authors contend that
the most important implication of their work may be a better
understanding of how computation shapes the physical world
around us. "If algorithmic concepts can be successfully
adapted to the molecular context," the authors write, "the
algorithm would join energy and entropy as essential concepts
for understanding how physical processes create order."
Winfree is an assistant professor of computation and neural
systems and computer science; Rothemund is a senior research
fellow in computer science and computation and neural systems.
The third author is Nick Papadakis, a former staff member in