Signal-passing Tile Assembly Model (STAM)

The Signal-passing Tile Assembly (STAM) is an asynchronous model of tile self-assembly which is considered as an extension of the 2-Handed Assembly Model (2HAM) and is based on active glues which can dynamically change state, allowing any action of turning a glue on or off, attaching a new tile, or breaking apart an assembly to happen in any order.In STAM basic tiles of the Tile Assembly Model (TAM) are augmented with the ability to receive information, in the form of signals, from neighboring tiles in an assembly, and to pass signals to neighboring tiles. A very important feature of signals is that each signal can only move across any given tile one time - they are not reusable .

Generalized model of STAM imposes minimal restrictions on aspects such as the speed of signals and orderings of events. This generalized version, while perhaps difficult to create well-behaved constructions within, provides a framework that is intended to be maximally independent of the specific details of potential physical implementations of actual signal tiles and enriches the tile assembly paradigm with greater capabilities that anticipate advancing techniques in the field of DNA nanotechnology and allow tile assembly to more closely emulate biological and natural processes.

The addition of signaled glue activation and deactivation to tile assembly brings it one step closer to emulating biological processes of self assembly, where communication within a developing and growing living organism are crucial to its survival and success. Communication between tiles and throughout assemblies allows them to take on changing roles in hierarchical assembly processes, resulting in production of organized entities that could continue to function as elements in further tile computation. The generalized model presented here has been designed to take into consideration a DNA implementation of all aspects of signaled assembly: binding, signaling, and glue activation or deactivation.

Physical Basis for the Model

The physical body of a tile might be composed entirely from a DNA origami structure which has more room for signal pathways than smaller DNA structures that have been used to implement the passive tiles of the TAM. Toe-hold mediated DNA strand exchange mechanisms , as shown in Figure 1, provide a basis for a plausible physical implementation of signaling, glue activation and glue deactivation. Signals across individual tiles could potentially be implemented using DNA hybridization cascades such as Hybridization Chain Reaction (HCR) , transducers , seesaw gates , other mechanisms , or by DNA walkers.

Figure.1: Activation of a latent glue. Single-stranded DNA is depicted as a line with an arrow at the 3' end and double-stranded DNA is shown as two parallel lines connected by a ladder of base pairs. Credit SIAM Journal on Computing

Letters such as a and \(y\) indicate short sequences of DNA bases and a star indicates the complementary sequence. Rectangles indicate structures, possibly composed of DNA origami, to which the relevant sticky ends of DNA are attached. a) The strand zbc is presumed to be unavailable until freed by a previous signaling cascade (not shown). The sequence labeled \(z\) may then bind at the toehold z8 on the protection strand \(c^{*} b^* z^*\), removing it from the glue strand abc via strand displacement. The protection strand is shown bound only to \(b\) and \(c\), which is enough to prevent interaction with the complementary tile edge shown as long as no toeholds are free to interact. Alternatively, the entire sequence abc could be blocked by the protection strand. b) Once the protection strand is removed, the glue strand abc is active or on. A glue may be considered 'latent'or 'off' if its DNA sticky end is blocked by being bound to a complementary DNA strand. Activation of a latent glue can be done by the toe-hold mediated removal of a protection strand that blocks a sticky end, (Figure 1). Deactivation can be accomplished by a toehold-mediated mechanism that is essentially the reverse of activation, whereby a protection strand can be released in the vicinity of the glue strand, covering up the sticky end used for binding. By adding more toeholds, one could add a finite number of cycles of activation and deactivation, but each would be mediated by a different activation and deactivation strand, and each effectively consumes DNA fuel. Thus, in the model we have limited activation to occurring only once. More instances of a glue can be added in a construction if needed.

STAM Notation and Model

High Level Description of the STAM

In the STAM, tiles are allowed to have sets of glues on each edge (as opposed to only one glue per side as in the TAM and 2HAM ). Tiles have an initial state in which each glue is either 'on' or 'latent' (i.e. can be switched on later). Tiles also each implement a transition function which is executed upon the binding of any glue on any edge of that tile. The transition function specifies a set of glues (along with the sides on which those glues are located) and an action for each:

1. turn that glue on (only valid if it is currently latent), or
2. turn that glue off (valid if it is currently on or latent).

Note that turning a glue off breaks any bond that that glue may have formed with a neighboring tile. The transition function defined for each tile type is allowed a unique set of output actions for the binding event of each glue along its edges. As the STAM is an extension of the 2HAM, binding and breaking can occur between pairs of arbitrarily sized supertiles. In order to allow for physical mechanisms which implement the transition functions of tiles but are arbitrarily slower or faster than the average rates of (super)tile attachments and detachments, rather than immediately enacting the outputs of transition functions, each output action is put into a set of "pending actions" which includes all actions which have not yet been enacted for that glue. An STAM system consists of a set of tiles and a temperature value. To define what is producible from such a system, we use a recursive definition of producible assemblies which starts with the initial tiles and then contains any supertiles which can be formed by doing the following to any producible assembly:

1. executing any entry from the pending actions of any one glue within a tile within that supertile (and then that action is removed from the pending set),
2. binding with another supertile if they are able for form a \(\tau\)-stable supertile, or 3. breaking apart into 2 separate supertiles along a cut whose total strength is less than \(\tau\).

Basic Notation

Let \(D\) denote the set of labels \(\{north, south, east, west\}\), or \(\{N,S,E,W\}\).

Active Glues and Glue States

Let \(\Gamma\) denote a set of \(glue types\). A \(glue\) is an ordered pair \((g,s)\) where \(g \in \Gamma\) is the glue type and \(s \in \mathbb{Z}\) is the glue \(strength\). Note that throughout the remainder of this paper, unless specifically stated, all glues will have strength \(1\) and as shorthand will be denoted simply by their glue types with the strength omitted.

Let \(Q = \{\texttt{latent}, \texttt{on}, \texttt{off}\}\) be the set of possible \(states\) for a glue. Intuitively, \(\texttt{on}\) is the ``normal, active state of a glue, meaning that it is either able to bind or currently bound. A glue in the \(\texttt{latent}\) state is inactive (and therefore unable to bind), and also has never been \(\texttt{on}\) (or \(\texttt{off}\)). A glue in the \(\texttt{off}\) state is also inactive and unable to bind, but can never be (re)activated. We define an \(active glue\) as an ordered pair \((g,q)\) where \(g \in \Gamma\) is a glue type and \(q \in Q\) is a state.

Fig. 2: The valid state transitions for active glues Credit:SIAM Journal on Computing

Active Labels

As in the original TAM, we define a \(label\) as an arbitrary string over some fixed alphabet and labels will be used as non-functional (i.e. they don't participate in tile bindings) means of identifying tile types. Denote as \(\Sigma\) the set of all valid labels. For the self-assembly of patterns (e.g. the weak self-assembly of the Sierpinski triangle), tile labels are the mechanism used for distinguishing between groups of tiles, i.e. those ``in the pattern and those ``outside it. Experimentally, labels can be implemented as DNA loops which protrude above the surfaces of tiles for imaging purposes , and thus the motivation exists to allow for the modification of tile labels along with glues. Therefore, we define an \(active label\) is an ordered pair \((x,q)\) where \(x \in \Sigma\) and \(q \in Q\).

Active Tiles and Transition Functions

A \(generalized active tile type\) \(t\) is a unit square defined as a \(4\)-tuple \(t = \left(G, L, \delta, \Pi\right)\) where \(G: D \rightarrow P(\Gamma \times Q)\) is a function specifying the set of all active glues present on a given side, \(L\) is the set of all active labels, \(\delta: D \times \Gamma \rightarrow P(((D \times \Gamma \times \{\texttt{on}, \texttt{off}\}) \cup (\Sigma \times \{\texttt{on}, \texttt{off}\}))\) is the \(transition function\) and \(\Pi\) is a multiset over \((D \times \Gamma \times \{\texttt{on}, \texttt{off}\}) \cup (\Sigma \times \{\texttt{on}, \texttt{off}\})\). A generalized active tile type \(t = (G, L, \delta, \Pi)\) is an \(active tile type\) if, for all \(d \in D\) and for all active glues \((g,q),(g',q') \in G(d)\), \(g \ne g'\). In other words, while a tile side may have multiple glues, there cannot be multiple copies of the same type of glue on a single side.

A transition function \(\delta\) takes as input a direction \(d \in D\) and a glue type \(g \in \Gamma\) (i.e. we say that it is ``fired by the binding of glue type \(g\) on side \(d\) of \(t\)), and outputs a (possibly empty) set of \(glue\) or \(label actions\), i.e., elements of \((D \times \Gamma \times \{\texttt{on}, \texttt{off}\}) \cup (\Sigma \times \{\texttt{on}, \texttt{off}\})\). Consider an active tile type \(t = (G, L, \delta, \Pi)\) and suppose that \((g,q) \in G(d)\) for some \(d \in D\) and \((d', g' ,q') \in \delta(d,g)\). Intuitively, if \(m = \Pi(d', q')\) (i.e., the \(multiplicity\) of \((d',q') \in \Pi\)) \(before\) \(\delta\) ``fires, then \(\Pi(d', q') = m + 1\) \(after\) executing \(\delta\). We assume for the sake of convenience that \(\delta\) outputs the empty set for any pair of direction and glue on which \(\delta\) is not explicitly defined. In other words, the binding of a glue on \(t\) fires the transition function, which can result in a set of ``requests for specific active glues and labels on \(t\) to transition into specified states.

Active Supertiles

Active supertiles in the STAM are defined similarly to supetiles in the 2HAM. Note that only glues which are in the \(\texttt{on}\) state can bind, and only those which are bound contribute to the \(\tau\)-stability of a supertile. When two \(\tau\)-stable supertiles can be translated so that they are non-overlapping and the abutting \(\texttt{on}\) glues can bind to create a cut strength of at least \(\tau\), we say that they are \(\tau\)-\(combinable\). A supertile \(A\) is said to be \(\tau\)-\(breakable\) into supertiles \(B\) and \(C\) if there exists a strength \(\tau' < \tau\) strength cut of the stability graph \(G_A\) that separates the tiles of \(A\) into supertiles \(B\) and \(C\).

Active Supertile Combination

Two active supertiles \(A\) and \(B\) may combine into active supertile \(C\) if the underlying supertiles for \(A\) and \(B\) are \(\tau\)-combinable into the underlying supertile for \(C\). When supertiles combine, all matched glues in the \(\texttt{on}\) state on the boundary between \(A\) and \(B\) are said to bind, and thus fire the transition functions of their respective tiles, causing the necessary states to be added to the pending sets of the targeted tiles.

Active Supertile Breaking

An active supertile \(A\) can break into active supertiles \(B\) and \(C\) if the underlying supertile for \(A\) has a cut of less than \(\tau\)-strength dividing \(A\) into the underlying supertiles for \(B\) and \(C\).