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)

b)

E

c)

d)

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.

computational universality

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.

modeling errors

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