


============

Self-assembly is a term used to describe systems in which a small number of simple components, each following local rules governing their interaction with each other, automatically assemble to form a target structure. Winfree @Winf98 introduced the abstract Tile Assembly Model (aTAM) – based on a constructive version of Wang tiling @Wang61 [@Wang63] – as a simplified mathematical model of Seeman's work @Seem82 in utilizing DNA to physically implement self-assembly at the molecular level. In the aTAM, the fundamental components are un-rotatable, but translatable square "tile types" whose sides are labeled with glue "labels" and "strengths." Two tiles placed next to each other *interact* if the glue labels on their abutting sides match, and a tile *binds* to an assembly if the total strength on all of its interacting sides exceeds the ambient "temperature," equal to 2 in this paper. The model is detailed more formally in Section \[sec-tile-assembly-model\].

Winfree @Winf98 demonstrated the computational universality of the aTAM by showing how to simulate an arbitrary cellular automaton with a tile assembly system. Building on these connections to computability, Rothemund and Winfree @RotWin00 investigated the minimum number of tile types needed to uniquely assemble an $n \times n$ square. Utilizing the theory of Kolmogorov complexity, they show that for any algorithmically random $n$, $\Omega\left(\frac{\log n}{\log \log n}\right)$ tile types are required to uniquely assemble an $n \times n$ square, and Adleman, Cheng, Goel, and Huang @AdChGoHu01 exhibit a construction showing that this lower bound is asymptotically tight.

Real-life implementations of the aTAM involve (at the present time) creating tile types out of DNA double-crossover molecules @RoPaWi04, copies of which can be created at an exponential rate using the polymerase chain reaction (PCR) @MolecularCloningLabManual. PCR technology has advanced to the point where it is automated by machines, meaning that *copies* of tiles are easy to supply, whereas the number of distinct tile *types* is a precious resource, costing much more lab time to create. Therefore, effort has been put towards developing methods of "programming" tile sets through methods other than hard-coding the desired behavior into the tile types. Such methods include *temperature programming* @KS06 [@Sum09], which involves changing the ambient temperature through the assembly process in order to alter which bonds are possible to break or create, and *staged assembly* @DDFIRSS07, which involves preparing different assemblies in different test tubes, which are then mixed after reaching a terminal state. Each of these models allows a *single* tile set to be reused for assembling different structures by programming different environmental conditions that affect the behavior of the tiles and therefore serve as an "input" to be processed by the tile set.

The "input specification model" used in this paper is known as *tile concentration programming*. If the tile assembly system is nondeterministic – if intermediate assemblies exist in which more than one tile type is capable of binding to the same position – and if the solution is well-mixed, then the relative concentrations of these tile types determine the probability that each tile type will be the one to bind. Tile concentrations affect the expected time before an assembly is completed (such a model is considered in @AdChGoHu01 and @BeckerRR06, for instance), but we ignore such running time considerations in the present paper. We instead focus on using the biased randomness of tile concentrations to guide a probabilistic shape-building algorithm, subject a certain kind of "geometric *space* bound"; namely, that the algorithm must be executed within the confines of the shape being assembled. This restriction follows from the monotone nature of the aTAM: once a tile attaches to an assembly, it never detaches.

We now describe related work. Chandran, Gopalkrishnan, and Reif @ChaGopRei09 show that a one-dimensional line of expected length $n$ can be assembled using $\Theta\left( \log n \right)$ tile types, subject to the restriction that all tile concentrations are equal. Furthermore, they show that this bound is tight for *all* $n$. Note that this is not tile concentration programming since the concentrations are forced to be equal. Nonetheless, they use the inherent randomness of binding competition to strictly improve the assembly capabilities of the aTAM; a simple pigeonhole argument shows that $n$ unique tile types are required to construct a line of length $n$ in the deterministic aTAM model. Two previous papers @BeckerRR06 [@KaoSchS08] deal directly with the tile concentration programming model. Becker, Rapaport, and Rémila @BeckerRR06 show that there is a *single* tile assembly system $\calT$ such that, for all $n\in\N$, setting the tile concentrations appropriately causes $\calT$ to assemble an $n' \times n'$ square, such that $n'$ has expected value $n$. However, $n'$ will have a large deviation from $n$ with non-negligible probability. Kao and Schweller @KaoSchS08 improve this result by constructing, for each $\delta,\epsilon > 0$, a tile assembly system $\calT$ such that setting the tile concentrations appropriately causes $\calT$ to assemble an $n' \times n'$ square, where $(1-\epsilon) n \leq n' \leq (1+\epsilon) n$ with probability at least $1-\delta$, for sufficiently large $n\in\Z^+$ (depending on $\delta$ and $\epsilon$).

Kao and Schweller asked whether a constant-sized tile assembly system could be constructed that, through tile concentration programming, would assemble a square of dimensions *exactly* $n \times n$, with high probability. We answer this question affirmatively, showing that, for each $\delta > 0$, there is a tile assembly system $\calT$ such that, for sufficiently large $n \in\Z^+$, there is an assignment of tile concentrations to $\calT$ such that $\calT$ assembles an $n \times n$ square with probability at least $1-\delta$. Therefore, with a constant number of tile types, any size square can be created entirely through the programming of tile concentrations. The primary technique is a tile set that, through appropriate tile concentration programming, forms a thin structure of height $O(\log n)$ and length $O(n^{2/3})$ (and for arbitrarily small $\epsilon > 0$, the length can be made $O(n^{\epsilon})$) and encodes the value of $n$ in binary. This binary string could be used to assemble useful structures other than squares, such as rectangles and other supersets of the sampling structure that are "easily encoded" in a binary string of length $O(\log n)$.

Kao and Schweller also asked whether arbitrary finite connected shapes, possibly scaled by factor $c\in\N$ (depending on the shape) by replacing each point in the shape with a $c \times c$ block of points, could be assembled from a constant tile set through concentration programming. Our construction answering the first question computes the binary expansion of $n$ with high probability in a self-assembled rectangle of height $O(\log n)$ and width $O(n^{2/3})$. By assembling this structure within the "seed block" of the construction of @SolWin07, our construction can easily be combined with that of @SolWin07 to answer this question affirmatively as well, by replacing the number $n$ with a program that outputs a list of points in the shape, and using this as the "seed block" of the construction of @SolWin07.

Since it may be infeasible to specify tile concentrations with unlimited precision, we show how to generalize our construction to allow a smooth tradeoff between specifying the number $n$ through tile concentrations versus hard-coded tile types. Since $\log n$ bits are required to specify $n$ for almost all values of $n$, we show that for arbitrary $g$, it is possible to specify "about" $g$ of the bits through tile concentrations and the remaining "about" $\log n - g$ bits through the hard-coding of tile types; i.e., using a tile set that can be described with about $(\log n) - g + o(\log n)$ bits. The actual bound is complicated and is stated in Theorem \[thm-tradeoff\].

Finally, there are some unrealistic aspects of the concentration programming model, in addition to the assumption that concentrations can be specified to unlimited precision. Chiefly, the aTAM is itself an kinetically implausible model, but Winfree showed that the behavior of the aTAM can be approximated to arbitrary accuracy by the more realistic *kinetic Tile Assembly Model* (kTAM) @Winf98. One of the assumptions Winfree employs to achieve this approximation is that all tile types have equal concentration, a condition clearly violated by our intentional setting of concentrations to be unequal. We will argue that our particular construction avoids the potential pitfalls of the concentration programming model, but leave open the task of defining a concentration programming model that is inherently immune to these pitfalls. We also show how to alter the construction to use only concentrations that are arbitrarily close to uniform, as a potential fix for the kinetic problems.

This paper is organized as follows. Section \[sec-tile-assembly-model\] provides background definitions and notation for the abstract TAM and tile concentration programming. Section \[sec-construction\] specifies and proves the correctness of the main construction, a tile set that can be used to assemble precisely-sized squares through concentration programming. This results of Section \[sec-construction\] first appeared in @RSAES. Section \[sec-shapes\] specifies the construction of a tile set that assembles scaled versions of arbitrary finite shapes through concentration programming. This scaled shapes construction was announced in @RSAES but not demonstrated. Section \[sec-tradeoff\] discusses a relaxation of the model that allows a greater than constant number of tile types, while using fewer bits to specify the concentrations of each tile type, and shows how to achieve a smooth tradeoff between the resources of "number of tile types" and "bits of precision of concentrations", to assemble squares, while using an asymptotically optimal number of total bits of precision (i.e., the bits of precision of concentrations, plus the bits needed to describe the tile types, are $O(\log n)$ for an $n \times n$ square). Section \[sec-unrealistic\] discusses some unrealistic aspects of the concentration programming model, and argues that the constructions of this paper are resistant to the problems caused by those unrealistic assumptions, or can be fixed to alleviate these problems. Section \[sec-conclusion\] concludes the paper, discusses practical limitations of the construction and potential improvements and states open questions.

{'source': 'arXiv_out/0901'}