lems. We can consider other types of errors. For instance, we consider some tile types to have input and output sides, although this is not enforced from within the model. Consider the following error: after some time, a portion of the assembly is removed to make a hole. This could result in “backward” growth filling in the hole using output glues, possibly resulting in the wrong tiles attaching (this would happen in Figure 2d since XOR is not a 1-1 function). Winfree57 introduced a 3 × 3 block transformation scheme called self-healing that enables the assembly to regrow correctly even when holes are blown out of the assembly, so long as the seed remains present. Soloveichik, Cook, and Winfree50 showed how to combine self-healing simultaneously with proofreading. Chen et al. 16 showed that a more extreme form of self-healing was possible for the particular task of assembling an n × n square from O(log n) tile types: the entire square is able to grow from any subassembly of width or height 2 log n, without requiring the seed. They also generalize the idea to arbitrary finite shapes (with some resolution loss).

Another type of error is spurious nucleation, in which tiles attach to each other without a seed, using strength 1 growth to form a stable assembly from which an incorrect assembly could grow. Schulman and Winfree showed both theoretically48 and experimentally49 that a certain class of tile systems can be made resistant to nucleation errors, in the sense that with the addition of O(k) extra tile types, in the absence of the seed, the probability is at most O( 2−k) that sufficiently many tiles aggregate to create a stable assembly from which further growth can occur.

The conclusion to draw from these error correction techniques is that, even though the aTAM does not accurately describe the behavior of DNA tiles, under certain assumptions, it is an implementable “programming language” for tile self-assembly.

tile complexity

We have identified the algorithmic aspect of self-assembly with the ability of a small number of tile types to assemble a large structure. This ability will prove crucial to programming large,

even though
the atam does
not accurately
describe the
behavior of Dna
tiles, under certain
assumptions, it is
an implementable
“programming
language” for tile
self-assembly.

complex molecular self-assembling systems, since the total number of types of molecular components dominates the cost (in money and time) of implementation.

To quantitatively formalize this idea, Rothemund and Winfree47 defined the tile complexity of a shape S (a finite, connected subset of Z2) to be the minimum number of tile types in any tile system—with a single seed tile— that uniquely assembles a single terminal assembly with shape S. The requirement of a size- 1 seed avoids cheating by simply letting the seed assembly have the desired shape. They studied the tile complexity of n × n squares, which has since become a canonical benchmark problem for studying various other aspects of self-assembly, since n × n squares are in a sense the simplest shape with non-trivial tile complexity. The simplest shape is a single point, whose tile complexity is clearly 1. The next simplest shape might be a 1 × n line. An easy argument shows that its tile complexity is n. Since it is one-dimensional, any stable assembly with that shape must use entirely double-strength glues to hold it together. If fewer than n tile types are used, then one must repeat, but this tile system would then be able to grow an infinite line by repeating the segment between the repetitions. Only in two dimensions is tile complexity nontrivial.

Rothemund and Winfree showed that for most values of n (all algorithmically random n), the tile complexity of an n × n square is Ω( log n log log n). Why does this hold? A tile system of size k can be described using O(k log k) bits (O(log k) bits per tile type). If the tile system uniquely self-assembles an n × n square, then that description, together with a constant size aTAM simulator, constitute a program of length O(k log k) that outputs n. Since for most n, the shortest program outputting n is log n bits long, we must have k log k = Ω(log n), that is, k = Ω( log n log log n). They then show that the tile complexity of all n × n squares is O(log n), in which log n tile types each represent a particular bit of n that assemble to form a 1 × log n row whose north glues represent n in binary. From this assembly, a O( 1) tile types attach to assemble an n × n square, first by growing a counter—essentially a bi-nary-to-unary converter—that counts