Program Size and Temperature in Self-Assembly

Abstract

Winfree’s abstract Tile Assembly Model is a model of molecular self-assembly of DNA complexes known as tiles, which float freely in solution and attach one at a time to a growing “seed” assembly based on specific binding sites on their four sides. We show that there is a polynomial-time algorithm that, given an $n \times n$ square, finds the minimal tile system (i.e., the system with the smallest number of distinct tile types) that uniquely self-assembles the square, answering an open question of Adleman et al. (Combinatorial optimization problems in self-assembly, STOC 2002). Our investigation leading to this algorithm reveals other positive and negative results about the relationship between the size of a tile system and its “temperature” (the binding strength threshold required for a tile to attach).

Appendix: Formal Definition of the Abstract Tile Assembly Model

This section gives a terse definition of the abstract Tile Assembly Model (aTAM, [29]). This is not a tutorial; for readers unfamiliar with the aTAM, [21] gives an excellent introduction to the model.

Fix an alphabet $\Sigma$. $\Sigma ^*$ is the set of finite strings over $\Sigma$. Given a discrete object $O$, $\langle O \rangle$ denotes a standard encoding of $O$ as an element of $\Sigma ^*$. $\mathbb {Z}$, $\mathbb {Z}^+$, $\mathbb {N}$, $\mathbb {R}^+$ denote the set of integers, positive integers, nonnegative integers, and nonnegative real numbers, respectively.

For a set $A$, $\mathcal {P}(A)$ denotes the power set of $A$. Given $A \subseteq \mathbb {Z}^2$, the full grid graph of $A$ is the undirected graph $G^\mathrm {f}_A=(V,E)$, where $V=A$, and for all $u,v\in V$, $\{u,v\} \in E \iff \Vert u-v\Vert _2 = 1$; i.e., if and only if $u$ and $v$ are adjacent on the integer Cartesian plane. A shape is a set $S \subseteq \mathbb {Z}^2$ such that $G^\mathrm {f}_S$ is connected.

A tile type is a tuple $t \in (\Sigma ^*)^4$; i.e., a unit square with four sides listed in some standardized order, each side having a glue label (a.k.a. glue) $\ell \in \Sigma ^*$. For a set of tile types $T$, let $\Lambda (T) \subset \Sigma ^*$ denote the set of all glue labels of tile types in $T$. Let $\{\mathsf {N},\mathsf {S},\mathsf {E},\mathsf {W}\}$ denote the directions consisting of unit vectors $\{(0,1), (0,-1), (1,0), (-1,0)\}$. Given a tile type $t$ and a direction $d \in \{\mathsf {N},\mathsf {S},\mathsf {E},\mathsf {W}\}$, $t(d) \in \Lambda (T)$ denotes the glue label on $t$ in direction $d$. We assume a finite set $T$ of tile types, but an infinite number of copies of each tile type, each copy referred to as a tile. An assembly is a nonempty connected arrangement of tiles on the integer lattice $\mathbb {Z}^2$, i.e., a partial function $\alpha :\mathbb {Z}^2 \dashrightarrow T$ such that $G^\mathrm {f}_{\mathrm{dom} \;\alpha }$ is connected and $\mathrm{dom} \;\alpha \ne \emptyset$. The shape of $\alpha$ is $\mathrm{dom} \;\alpha$. Given two assemblies $\alpha ,\beta :\mathbb {Z}^2 \dashrightarrow T$, we say $\alpha$ is a subassembly of $\beta$, and we write $\alpha \sqsubseteq \beta$, if $\mathrm{dom} \;\alpha \subseteq \mathrm{dom} \;\beta$ and, for all points $p \in \mathrm{dom} \;\alpha$, $\alpha (p) = \beta (p)$.

A strength function is a function $g:\Lambda (T)\rightarrow \mathbb {N}$ indicating, for each glue label $\ell$, the strength $g(\ell )$ with which it binds. Let $\alpha$ be an assembly and let $p\in \mathrm{dom} \;\alpha$ and $d\in \{\mathsf {N},\mathsf {S},\mathsf {E},\mathsf {W}\}$ such that $p + d \in \mathrm{dom} \;\alpha$. Let $t=\alpha (p)$ and $t' = \alpha (p+d)$. We say that the tiles $t$ and $t'$ at positions $p$ and $p+d$ interact if $t(d) = t'(-d)$ and $g(t(d)) > 0$, i.e., if the glue labels on their abutting sides are equal and have positive strength. Each assembly $\alpha$ induces a binding graph $G^\mathrm {b}_\alpha$, a grid graph $G=(V_\alpha ,E_\alpha )$, where $V_\alpha =\mathrm{dom} \;\alpha$, and $\{p_1,p_2\} \in E_\alpha \iff \alpha (p_1) \text { interacts with } \alpha (p_2)$.¹¹ Given $\tau \in \mathbb {Z}^+$, $\alpha$ is $\tau$ -stable if every cut of $G^\mathrm {b}_\alpha$ has weight at least $\tau$, where the weight of an edge is the strength of the glue it represents. That is, $\alpha$ is $\tau$-stable if at least energy $\tau$ is required to separate $\alpha$ into two parts. When $\tau$ is clear from context, we say $\alpha$ is stable.

A tile assembly system (TAS) is a triple $\mathcal {T}= (T,\sigma ,g,\tau )$, where $T$ is a finite set of tile types, $\sigma :\mathbb {Z}^2 \dashrightarrow T$ is the finite, $\tau$-stable seed assembly, $g:\Lambda (T)\rightarrow \mathbb {N}$ is the strength function, and $\tau \in \mathbb {Z}^+$ is the temperature. Given two $\tau$-stable assemblies $\alpha ,\beta :\mathbb {Z}^2 \dashrightarrow T$, we write $\alpha \rightarrow _1^{\mathcal {T}} \beta$ if $\alpha \sqsubseteq \beta$ and $|\mathrm{dom} \;\beta \setminus \mathrm{dom} \;\alpha | = 1$. In this case we say $\alpha$ $\mathcal {T}$ -produces $\beta$ in one step.¹² If $\alpha \rightarrow _1^{\mathcal {T}} \beta$, $\mathrm{dom} \;\beta \setminus \mathrm{dom} \;\alpha =\{p\}$, and $t=\beta (p)$, we write $\beta = \alpha + (p \mapsto t)$. The $\mathcal {T}$ -frontier of $\alpha$ is the set $\partial ^\mathcal {T}\alpha = \bigcup _{\alpha \rightarrow _1^\mathcal {T}\beta } \mathrm{dom} \;\beta \setminus \mathrm{dom} \;\alpha$, the set of empty locations at which a tile could stably attach to $\alpha$.

A sequence of $k\in \mathbb {Z}^+ \cup \{\infty \}$ assemblies $\varvec{\alpha } = (\alpha _0,\alpha _1,\ldots )$ is a $\mathcal {T}$ -assembly sequence if, for all $1 \le i < k$, $\alpha _{i-1} \rightarrow _1^\mathcal {T}\alpha _{i}$. We write $\alpha \rightarrow ^\mathcal {T}\beta$, and we say $\alpha$ $\mathcal {T}$ -produces $\beta$ (in 0 or more steps) if there is a $\mathcal {T}$-assembly sequence $\varvec{\alpha }=(\alpha _0,\alpha _1,\ldots )$ of length $k = |\mathrm{dom} \;\beta \setminus \mathrm{dom} \;\alpha | + 1$ such that 1) $\alpha = \alpha _0$, 2) $\mathrm{dom} \;\beta = \bigcup _{0 \le i < k} \mathrm{dom} \;{\alpha _i}$, and 3) for all $0 \le i < k$, $\alpha _{i} \sqsubseteq \beta$. In this case, we say that $\beta$ is the result of $\varvec{\alpha }$, written $\beta =\mathrm res (\varvec{\alpha })$. If $k$ is finite then it is routine to verify that $\mathrm res (\varvec{\alpha }) = \alpha _{k-1}$.¹³ We say $\alpha$ is $\mathcal {T}$ -producible if $\sigma \rightarrow ^\mathcal {T}\alpha$, and we write $\mathcal {A}[\mathcal {T}]$ to denote the set of $\mathcal {T}$-producible canonical assemblies. The relation $\rightarrow ^\mathcal {T}$ is a partial order on $\mathcal {A}[\mathcal {T}]$ [17, 19].¹⁴ A $\mathcal {T}$-assembly sequence $\alpha _0,\alpha _1,\ldots$ is fair if, for all $i$ and all $p\in \partial ^\mathcal {T}\alpha _i$, there exists $j$ such that $\alpha _j(p)$ is defined; i.e., no frontier location is “starved”.

An assembly $\alpha$ is $\mathcal {T}$ -terminal if $\alpha$ is $\tau$-stable and $\partial ^\mathcal {T}\alpha =\emptyset$. It is easy to check that an assembly sequence $\varvec{\alpha }$ is fair if and only $\mathrm res (\varvec{\alpha })$ is terminal. We write $\mathcal {A}_{\Box }[\mathcal {T}] \subseteq \mathcal {A}[\mathcal {T}]$ to denote the set of $\mathcal {T}$-producible, $\mathcal {T}$-terminal canonical assemblies.

A TAS $\mathcal {T}$ is directed (a.k.a., deterministic, confluent) if the poset $(\mathcal {A}[\mathcal {T}], \rightarrow ^\mathcal {T})$ is directed; i.e., if for each $\alpha ,\beta \in \mathcal {A}[\mathcal {T}]$, there exists $\gamma \in \mathcal {A}[\mathcal {T}]$ such that $\alpha \rightarrow ^\mathcal {T}\gamma$ and $\beta \rightarrow ^\mathcal {T}\gamma$.¹⁵ We say that a TAS $\mathcal {T}$ strictly self-assembles a shape $S \subseteq \mathbb {Z}^2$ if, for all $\alpha \in \mathcal {A}_{\Box }[\mathcal {T}]$, $\mathrm{dom} \;\alpha = S$; i.e., if every terminal assembly produced by $\mathcal {T}$ has shape $S$. If $\mathcal {T}$ strictly self-assembles some shape $S$, we say that $\mathcal {T}$ is strict. Note that the implication “$\mathcal {T}$ is directed $\implies$ $\mathcal {T}$ is strict” holds, but the converse does not hold. We say that $\mathcal {T}$ uniquely self-assembles a shape $S$ if $\mathcal {T}$ is directed and it strictly self-assembles $S$.

When $\mathcal {T}$ is clear from context, we may omit $\mathcal {T}$ from the notation above and instead write $\rightarrow _1$, $\rightarrow$, $\partial \alpha$, frontier, assembly sequence, produces, producible, and terminal.

We also assume without loss of generality that every single glue or double glue occurring in some tile type in some direction also occurs in some tile type in the opposite direction, i.e., there are no “effectively null” single or double glues.