form, the sorcery of DNA solutions to
NP-complete problems proceeds by
letting the DNA test all possible solutions in parallel in a single test tube.
Assuming a modest solution length of
300 bits, squeezing 2300 molecules into
a test tube is like installing 2300 processors in a parallel computer: there is not
enough sand in the world to supply
that much silicon.
Scientific journals continue to
traffic in tales of DNA’s exponential
search capability. As with Mjölnir, the
mountain-crushing hammer of Thor,
the time has come to place these tales
into the dustbin of mythology, making room for the real—and far more
exciting—scientific work that remains
to be done in molecular computing. If
there is a breakthrough in molecular
engineering that will enable the solution of classically intractable problems, it will have to come from quantum mechanics or perhaps from some
exotic physical theory yet to be discovered. It will not come about solely
by replacing silicon with DNA. But
enough pessimism; let’s find out what
DNA can do.
figure 2. abstract tile assembly model (atam).
a) double-crossover tile with four sticky end.
b) representation of a tile as a square with sides labeled by string “glues.”
c) seven tile types. bond strengths indicated by the number of small black squares on a side:
total strength 2 is required to attach a tile to a partially formed assembly of tiles. one tile type
is designated as the seed, from which growth is assumed to nucleate.
d) growth of the tiles into an assembly with the discrete sierpinski triangle pattern.
Winfree56 showed that the aTAM is
computationally universal, that is, able
to simulate any algorithm. This one
fact explains the richness of the theory presented in the rest of the article.
What exactly does it mean?
The model as stated lacks one feature in common with other computational models: there is no input! One
potential way to program a single tile
set with different inputs that result in
different behaviors is to generalize the
idea of a single seed tile type to a larger
seed assembly. Within the model, we
allow the seed assembly to be any finite
stable assembly (“stable”= all cuts of
the assembly that separate it into two
components must break bonds of total
strength at least 2). In practice, seed
assemblies are not necessarily made
of tiles, but must simply have a perimeter compatible with the tiles, such as
a DNA origami shape appropriately
augmented with sticky ends on its side
(Figure 1g–h). We use the term tile system to refer to a finite set of tile types,
together with other parameters needed
to determine its behavior, such as its
seed assembly σ and its temperature τ.
With this convention established,
we can now state more formally what
it means to claim that the aTAM is
computationally universal. For every
single-tape Turing machine M, there
is a tile set T so that, for every input
string x, there is a seed assembly σ of T
so that T with seed σ uniquely assembles a space-time configuration transcript of M on input x.a By “uniquely
assembles,” we mean that although T
with seed σ assembles many different
partial assemblies, it has a unique terminal assembly α (terminal = no tile
can attach to it). The tth row of α represents the configuration of M(x) at time
step t, with σ occupying the first row.
The computational universality
of the a TAM implies that arbitrary algorithms may be executed by self-assembling tiles and therefore used to
direct the growth of the tiles. However,
the a TAM is not just another programming language. The subtle interplay of
computation and geometry in self-assembly gives rise to unique characteristics such as the distinction between
a σ is a 1 ×|x| row encoding x in a standard way;
we are not cheating by embedding the entire
computation M(x) into σ.
computable patterns and self-assembling patterns discussed later.
The aTAM is not a realistic model of
how DNA tiles actually behave at the
molecular level. In particular, it makes
two assumptions known not to hold in
practice: that tiles never detach from
an assembly, and that tiles only attach
when their binding strength exceeds
the temperature threshold value τ.
Winfree56 introduced the kinetic Tile
Assembly Model (k TAM) as a more realistic model of tile assembly that uses
standard laws of chemical kinetics to
relax these assumptions. Each tile
type is assumed to attach to any binding site on an assembly α, producing a
new assembly β, at a rate proportional
to its concentration, regardless of its
strength of attachment. If we assume
that there is only a single seed tile,
and that each other tile type is equally
concentrated (and much higher count
than 1, so that their rate of depletion
is essentially 0), then this forward rate
is equal for all tile types and approximately constant over time. Call this
forward rate rf . Each tile within β is assumed to detach at a rate proportional