one region of the scaffold with its left half and another region of the scaffold with its right half, bringing the two regions together. A more experimentally challenging technique, DNA tile assembly, is the physical basis for the theoretical work discussed in this article. A DNA tile is a DNA complex with four short single-stranded “sticky” ends protruding from it (see Figure 2a), which are intended to bind the tile to other tiles having sticky ends that are Watson-Crick complementary. Figure 1 shows images of some patterns that have been experimentally assembled with DNA tiles. Figure 2 shows how a DNA tile is modeled as a square with four sides having “specific glues.” DNA origami in its current incarnation is non-algorith-mic self-assembly, whereas DNA tile assembly is potentially algorithmic. We now explain this distinction.

Turing54 stated, “The ‘computable’
numbers may be described briefly as
the real numbers whose expressions
as a decimal are calculable by finite
means.” Finite means is formally equat-
ed with algorithm (for example, a Tur-
ing machine, a λ-expression, a Python
program, or an appropriately initial-
ized configuration of Conway’s Game
of Life). There are uncountably many
real numbers but only a countable
number of algorithms, so most real
numbers are not computable. What if
we wish to make sense of the question,
which integers are computable? By Tur-
ing’s qualitative definition, they are
all computable, but it is reasonable to
object that some integers (for example,
n = 1010,000) are easier to compute than
others (for example, m = a random se-
quence of 10,000 digits), in the sense
that a much smaller program suffices
to compute n than to compute m. To
make formal sense of such intuition,
the theory of Kolmogorov complexity33
gives a rigorous quantitative measure
of the “algorithmic complexity” of an
integer (or any other “finite object”
such as a finite string or a graph): the
length in bits of the shortest algorithm
that prints the integer and halts.

figure 1. experiments with double-crossover tiles.

mation is available to guide its attachment. DNA origami therefore does not constitute algorithmic self-assembly, since each staple strand “hardcodes” its position in the final structure. DNA tile assembly, however, has the potential to reuse a small number of tile types to create large structures.

Our combinatorial model of the dynamic behavior of these tiles is called the abstract Tile Assembly Model (aTAM), due to Winfree, 56 explained briefly in Figure 2. Figure 2c shows seven tile types that fill the entire second quadrant with a painting of the discrete Sierpinski triangle, showing that this pattern is “algorithmically self-assem-blable.” The main computation is done by the bottom four rule tile types using cooperative binding, which refers to the fact that a tile with only strength- 1 glues cannot bind to an assembly unless at least two of them match. ( Sometimes this binding strength threshold is called the “temperature” τ, which is usually 2 but not always.) The rule tiles in this example always bind using their south and east glues. Thus the glue labels (bits in this case) can be imagined as inputs to a function computed by the rule tile types (analogous to a transition function in a Turing machine or cellular automaton). The output of the function in this example is the XOR of the bits, which is advertised on the north and west sides.

 

a) b) c) 300 nm 100 nm

d)

g)

e)

10 nm 10 nm

50 nm f)

100 nm

100 nm h) 50 nm

Atomic force microscopy measures the height of a structure on a surface (mica). some tile types may have attached hairpins as “labels” (appearing white in images). a) lattice of tiles (single tile type). 59 b) sierpinski triangle in a lattice, no proofreading. 46 c) binary counter in a ribbon, no proofreading. 6 d) standard (left) versus snaked (right) proofreading for suppression of facet errors. 17 e) sierpinski triangle in a ribbon, no proofreading. 28 f) ribbons with zig-zag tiles for suppression of spurious nucleation. 49 g) ribbons nucleating from origami seed, copying a bit string, with proofreading. 7 h) ribbons nucleating from origami seed, executing a binary counter, with partial proofreading. 7

Parallelism in molecular
computing: the bad news

Algorithmic self-assembly is a subfield of molecular computing, highlighted in a news article by Kirk. L. Kroeker in the December 2011 issue of Communications. The field was initiated in 1994 when Adleman, 1 in a landmark proof-of-concept experiment, designed DNA molecules that interact to solve a 7-vertex case of the Hamiltonian path problem: executing a “DNA algorithm” whose basic operations are well-understood chemical interactions such as hybridization.

Let us state an unequivocal limitation to the power of molecular computing as a model of computation, which applies to algorithmic self-assembly systems as well. Molecular computing is not a magical potion that can be ladled over NP-complete problems to transubstantiate them into tractable problems. In its most generic