View source for Signal-passing Tile Assembly Model (STAM)

The Signal-passing Tile Assembly (STAM)<ref name="JMRSNR" /> is an asynchronous model of tile self-assembly which is considered as an extension of the 2-Handed Assembly Model ([[Two-Handed Assembly Model (2HAM)|2HAM]])<ref name="AGKS05g" /> and is based on active glues which can dynamically change state, allowing any action of turning a glue <tt>on</tt> or <tt>off</tt>, attaching a new tile, or breaking apart an assembly to happen in any order.In STAM basic tiles of the Tile Assembly Model ([[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 <ref name="JEWKNC" />.

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.<ref name="JEWKNC" />

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.

__TOC__


==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 [[Tile Assembly Model|TAM]]. Toe-hold mediated DNA strand exchange mechanisms <ref name="GSDSDY3" /><ref name="PYHCCR4" /><ref name="BYATAPF5" /> <ref name="DYZGS6"/>, 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) <ref name="RMDNA7" />, transducers <ref name="GSDSDY8"/>, seesaw gates <ref name="LQEWN9"/>, other mechanisms <ref name="PYHCR10"/>, or by DNA walkers. <ref name="KLMNDJ11"/><ref name="TORSNC12"/><ref name="SFMYKH13"/><ref name="FLRSNC15"/>

[[File:Activation_of_a_latent_glue.jpg|thumb|300px| alt= Activation of a latent glue| Figure.1: Activation of a latent glue.| alt=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: Asynchronous Signal Passing for Tile Self-Assembly: Fuel Efficient Computation and Efficient Assembly of Shapes ]]


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 <tt>'latent'</tt>or <tt>'off'</tt> 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 [[Two-Handed Assembly Model (2HAM)|2HAM]] ). Tiles have an initial state in which each glue is either <tt>'on'</tt> or  <tt>'latent'</tt> (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: 
# turn that glue on (only valid if it is currently latent), or  
#turn that glue off (valid if it is currently on or latent). 

This means that glues can only be <tt>on</tt> once (although may remain so for an arbitrary amount of time or permanently), either by starting in that state or being switched on from latent, and if they are ever switched to off then no further transitions are allowed for that glue. This essentially provides a single “use” of a glue (and thus the implicit signal sent by its activation and binding). 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 [[Two-Handed Assembly Model (2HAM)|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:
#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), 
#binding with another supertile if they are able for form a $\tau$-stable supertile, or  
#breaking apart into 2 separate supertiles along a cut whose total strength is less than $\tau$.

As an overview, tiles in the STAM pass signals to neighboring tiles simply by activating glues which can bind with glues on adjacent edges of neighboring tiles. The information content of a signal is dependent upon the transition function of the receiving tile, that is, by what glue actions the receiving tile initiates upon the binding of its glue. By subsequently activating and deactivating its own glues, the receiving tile can propagate the signal to any of its neighbors. Solely by utilizing the mechanism of glue activation and deactivation initiated and carried out on individual tiles but chained together through series of glue bindings, a global network which is capable of passing information across entire assemblies (and also of allowing them to selectively enable sites for further growth or to discard arbitrary portions of the assembly), is created. However, an important restriction is the ''fire once'' nature of the signals, meaning that each glue can only transition to any given state once, and therefore the number of signals which a tile can process is a constant dependent upon the definition of the tile type.



===Formal Definition of the Signal Passing Tile Assembly Model===

'''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$ = {<tt>latent</tt>, <tt>on</tt>, <tt>off</tt>} 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.

[[File:The_valid_state_transitions_for_active_glues.jpg|thumb|300px|Fig. 2: The valid state transitions for active glues
Credit:Asynchronous Signal Passing for Tile Self-Assembly: Fuel Efficient Computation and Efficient Assembly of Shapes]]


'''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 <ref name="FLRSNC15"/>, 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$.



===Producible Assemblies===
The signal passing tile assembly model is defined in terms of the set of producible active supertiles $P_{T ,\tau}$ .
$P_{T ,\tau}$ is defined recursively as follows:

'''Base Set of Assemblies'''  $ T \subseteq P_{T ,\tau}}$

'''Combination Transition''' For any 2 active supertiles $A, B \in P_{T ,\tau}$, if $A$ and $B$ are $\tau$ -combinable into active supertile $C$, then $C \in P_{T ,\tau}$ .

'''Break Transition''' For any supertile $A \in P_{T ,\tau}$ , if $A$ is  $\tau$-breakable into active supertiles $B$ and $C$, then $B, C \in P_{T ,\tau}$ .

'''Active Glue Transition'''  Consider an active supertile $A \in P_{T ,\tau}$ . For each active tile $t \in A$ with $A(x, y) = t = (G, L, \delta, \Pi)$, for all $d \in D$, for all $(g, p) \in G(d)$ and for all $(d, g, q) \in \Pi$, there is a supertile $B \in P_{T ,\tau}$ such that $A$ and $B$ differ only at location $(x, y)$ as follows: $B(x, y) = t$

# $\Pi'= \Pi-\{(d, g, q)\}$ and if
# $p = \texttt{on}$ and $q = \texttt{off}$ or $p = \texttt{latent}$ and $q = \texttt{off}$ or $p = \texttt{latent}$ and $q = \texttt{on}$, then for all $d\neq d$
(This simply says that any supertile B which can be created from another producible supertile $A$ by simply executing one of A’s pending actions is also producible.)

Active Label Transition Active label transitions are defined similar to active glue transitions.
(This simply says that any supertile B which can be created from another producible supertile A bysimply executing one of A’s pending actions is also producible.)

'''Active Label Transition''' Active label transitions are defined similar to active glue transitions.


===Terminal Assemblies===
The set of producible assemblies of an STAM system defines the collection of active supertiles that can occur throughout the assembly process. The terminal set of assemblies $A_{\square}[T, \tau ]$ of an STAM system (T, $\tau$ ) defines the subset of producible assemblies for which no combination, break, glue transition, or label transition is possible. Conceptually, the terminal assembly set represents the sink state of the assembly system in which the system has been given enough time for all assemblies to reach a terminal state. The terminal set of assemblies is considered the output of an STAM system.


==Example STAM System==
===Example tile types===
Figure 3 shows a tile set that will be used for the following example. Active tiles are referred by their labels for convenience. The “Bot” tile has four glue actions defined for its transition function, all of which turn <tt>on</tt> glues. The “MM” tile includes two glue actions which turn <tt>off</tt> glues: when glue ''e'' on the North binds, both that glue and glue b on the South get $\texttt{off}$ transitions placed into the $\Pi$ multiset of the active tile, which will eventually cause them to be turned <tt>off</tt>. The transition function for the “MR” tile contains a label action, namely when the $c$ glue on the South binds.

[[File:Example_of_STEM.jpg|thumb|300px|Figure 3. An example active tile set. Credit Asynchronous Signal Passing for Tile Self-Assembly: Fuel Efficient Computation and Efficient Assembly of Shapes]]




===Example STAM transitions===
[[File:Producible_supertiles.jpg|thumb|300px|Figure 4(a). Producible supertiles Credit: Asynchronous Signal Passing for Tile Self-Assembly: Fuel Efficient Computation and Efficient Assembly of Shapes]]
Define an STAM system $(T, 2)$ where $T$ is the tile set shown in Figure 3. Figure 4 shows a set of transitions and producible assemblies within that system. Figure 4(a) shows a “Top” and “MM” tile in their initial configurations (with empty $\Pi$ sets for all active tiles as required, and all superscripts explicitly shown for reference). Figure 4(b) shows the supertile resulting from a combination transition performed on one “Top” and one “MM” tile. Note that the binding of the two $e$ glues causes four glues to have state transitions added to the $\Pi$ multisets the belong to their respective active tile. Figure 4(c) shows the supertile resulting from a glue flip transition performed on the supertile in Figure 4(b), namely the $tl$ glue <tt>on</tt> the West side of the “Top” tile transitioned to state <tt>on</tt> and that pending transition was removed from the $\Pi$ multiset belonging to its active tile. Figure 4(d) shows the supertile resulting after two glue flip transitions are performed on the supertile in Figure 4(c), namely glue $tr$ <tt>on</tt> the East of “Top” is turned <tt>on</tt> and $e$ on the North of “MM” is turned <tt>off</tt>.

[[File:Example_transitions_for_the_tile_types.jpg|thumb|300px|Figure 4(b,c). An Example transition for the tile types. Credit: Asynchronous Signal Passing for Tile Self-Assembly: Fuel Efficient Computation and Efficient Assembly of Shapes]]

==References==

<references>

<ref name="AGKS05g"><bibtex> 
@article{AGKS05g,
  author =	"Qi Cheng and Gagan Aggarwal and Michael H. Goldwasser and Ming-Yang Kao and Robert T. Schweller and Pablo Moisset de Espanés",
  title =	"Complexities for Generalized Models of Self-Assembly",
  journal =	"SIAM Journal on Computing",
  volume = "34",
  pages = 	"1493--1515",
  year =	"2005",
}
</bibtex></ref>

<ref name="JMRSNR"><bibtex> 
@article{JMRSNR,
  author =	"Jennifer E. Padilla, Matthew J. Patitz, Raul Pena, Robert T. Schwellery, Nadrian C. Seeman, Robert Sheline, Scott M. Summers, and Xingsi Zhong",
  title =	"Asynchronous Signal Passing for Tile Self-Assembly: Fuel Efficient Computation and Efficient Assembly of Shapes",
  journal =	"Unconventional Computation and Natural Computation Lecture Notes in Computer Science",
  volume = "7956",
  pages = 	"174-185",
  year =	"2013",
}
</bibtex></ref>

<ref name="JEWKNC"><bibtex> 
@article{JEWKNC,
  author =	"J.E. Padilla, W. Liu, and N.C. Seeman",
  title =	"Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model",
  journal =	"Natural Computation",
  volume = "11",
  number = "2",
  pages = 	"323–338",
  year =	"2012",
}
</bibtex></ref>

<ref name="GSDSDY3"><bibtex> 
@article{GSDSDY,
  author =	"G. Seelig, D. Soloveichik, D.Y. Zhang, and E. Winfree",
  title =	"Enzyme-free Nucleic Acid Logic Circuits",
  journal =	"Science",
  volume = "314",
  number = "5805",
  pages = 	"1585-1588",
  year =	"2006",
}
</bibtex></ref>

<ref name="PYHCCR4"><bibtex> 
@article{PYHCCR4,
  author =	"P. Yin, H.M.T. Choi, C.R. Calvert, and N.A. Pierce",
  title =	"Programming biomolecular self-assembly pathways",
  journal =	"Nature",
  volume = "451",
  number = "7176",
  pages = 	"318-322",
  year =	"2008",
}
</bibtex></ref>

<ref name="BYATAPF5"><bibtex> 
@article{BYATAPF5,
  author =	"B. Yurke, A.J. Turberfield, A.P. Mills, F.C. Simmel, and J.L. Neumann",
  title =	"A DNA-fuelled molecular machine made of DNA",
  journal =	"Nature",
  volume = "406",
  number = " 6796",
  pages = 	"605-608",
  year =	"2000",
}
</bibtex></ref>

<ref name="DYZGS6"><bibtex> 
@article{DYZGS6,
  author =	"D.Y. Zhang and G. Seelig",
  title =	"Dynamic DNA nanotechnology using strand-displacement reactions",
  journal =	"Nature Chemistry",
  volume = "3",
  number = " 2",
  pages = 	"103-113",
  year =	"2011",
}
</bibtex></ref>


<ref name="RMDNA7"><bibtex> 
@article{RMDNA7,
  author =	"R.M. Dirks and N.A. Pierce",
  title =	"Triggered amplification by hybridization chain reaction",
  journal =	"Proceedings of the National Academy of Sciences of the United States of America",
  volume = "101",
  number = "43",
  pages = 	"15275–15278",
  year =	"2004",
}
</bibtex></ref>

<ref name="GSDSDY8"><bibtex> 
@article{GSDSDY8,
  author =	"G. Seelig, D. Soloveichik, D.Y. Zhang, and E. Winfree",
  title =	"Enzyme-free nucleic acid logic circuits",
  journal =	"Science",
  volume = " 314",
  number = "5805",
  pages = 	"1585",
  year =	"2006",
}
</bibtex></ref>

<ref name="LQEWN9"><bibtex> 
@article{LQEWN9,
  author =	"L. Qian and E. Winfree",
  title =	"A simple DNA gate motif for synthesizing large-scale circuits",
  journal =	"DNA Computing",
  volume = "5347",
  pages = 	"70-89",
  year =	"2009",
}
</bibtex></ref>

<ref name="PYHCR10"><bibtex> 
@article{PYHCR10,
  author =	"P. Yin, H.M.T. Choi, C.R. Calvert, and N.A. Pierce",
  title =	"Programming biomolecular self-assembly pathways",
  journal =	"Nature",
  volume = "451",
  number = "7176",
  pages = 	"318-322",
  year =	"2008",
}
</bibtex></ref>

<ref name="KLMNDJ11"><bibtex> 
@article{KLMNDJ11,
  author =	"K. Lund, A.J. Manzo, N. Dabby, N. Michelotti, A. Johnson-Buck, J. Nangreave, S. Taylor, R. Pei, M.N. Stojanovic, and N.G. Walter",
  title =	"Molecular robots guided by prescriptive landscapes",
  journal =	"Nature",
  volume = "465",
  number = "7295",
  pages = 	"206-210",
  year =	"2010",
}
</bibtex></ref>

<ref name="TORSNC12"><bibtex> 
@article{TORSNC12,
  author =	"T. Omabegho, R. Sha, and N.C. Seeman",
  title =	"A bipedal DNA brownian motor with coordinated legs",
  journal =	"Science",
  volume = "324",
  number = "5923",
  pages = 	"67",
  year =	"2009",
}
</bibtex></ref>

<ref name="SFMYKH13"><bibtex> 
@article{SFMYKH13,
  author =	"S.F.J. Wickham, M. Endo, Y. Katsuda, K. Hidaka, J. Bath, H. Sugiyama, and A.J. Turberfield",
  title =	"Direct observation of stepwise movement of a synthetic molecular transporter",
  journal =	"Nature Nanotechnology",
  volume = "6",
  number = "3",
  pages = 	"166-169",
  year =	"2011",
}
</bibtex></ref>

<ref name="FLRSNC15"><bibtex> 
@article{FLRSNC15,
  author =	" F. Liu, R. Sha, and N.C. Seeman",
  title =	" Modifying the surface features of two-dimensional DNA crystals",
  journal =	"Journal of the American Chemical Society",
  volume = "121",
  number = "5",
  pages = 	"917-922",
  year =	"1999",
}
</bibtex></ref>


</references> 

[[Category: Tile Assembly Models]]
[[Category:Self-assembly]]