
\blankpage

\chapter{Notation}
\label{ch02}

\section{State Description}

\subsection{Labeling}


Rather than explicitly listing every base
and all base-pairings, we abstract the
notation to use \textit{labels} to refer
\index{label standing for single strand of bases}%
to a particular sequence of bases (in the 5' to 3' direction).
A single letter $a$ may then be used to
stand for the entire sequence of a single strand, such as \texttt{GATTACA}.
The complement of such a sequence can
then be denoted by a horizontal hat. 
\index{complement notation: horizontal hat }%
\index{notation: horizontal hat or bar indicates complement}%
For example, $\overline
a$ would denote the sequence \texttt{TGTAATC} (again in the 5' to 3'
direction).
\index{complement as shorthand for reverse complement}%
Square brackets will be used to demarcate
a complex, so that the very simple example
\index{notation: complex demarcated by brackets}%
of a single strand of sequence
$a$, with un-ligated 5' and 3' ends, would then be represented as $[a]$.
%
\begin{figure}[hbt]
	\centering
	\includegraphics{ch2-fig01.eps}
	\caption[A small non-empty complex]{$[a]$
The smallest non-empty complex consists of just a single letter.}
	\label{fig:a}
\end{figure}

If there are multiple labels---$a$ is
\texttt{GCTT} and $b$ is \texttt{ATAC}---then
concatenation denotes their ligation.
\index{ligation}%
\index{notation: concatenation indicates ligation}%
Thus, $[ a b \overline a ]$ is a single 
strand with the sequence \texttt{GCTTATACAAGC};
note that $\overline a$ is \texttt{AAGC}.
%
\begin{figure}[hbt]
	\centering
	\includegraphics{ch2-fig02.eps}
	\caption[A complex demonstrating ligation]{A
complex demonstrating ligation $[a b \overline a]$ }
	\label{fig:abA}
\end{figure}

Although we do not use such structures,
if a single strand
is ligated into a loop, this can be specified
by enclosing a strand in parenthesis $[(a
b \overline a)]$, denoting that the 5' end hybridizes to the 3' end.
\index{notation: parentheses indicate loop}%
This implies that the labels
can be ``rotated'' and specify the same complex
as in Figure~\ref{fig:abA_loop}.
%
\begin{figure}[hbt]
	\centering
	\includegraphics{ch2-fig03.eps}
	\caption[A loop strand]{The loop strand
$[(a b \overline a)] = [(b \overline a a )] = [(\overline a a b)] $ }
	\label{fig:abA_loop}
\end{figure}


Because there may be many copies of a label
in a single machine, a \textit{segment}
refers to a particular instance of a labeled
single strand. 
\index{segment as instance of a strand}%
\index{strand vs. segment}%
\index{index, segment}%
\index{notation: index indicates instance of strand}%
Each segment is identified by an index.
For example, in the complex $[a_0 b a_1]$, 
segment $a_0$ refers to the segment
at the 5' end of the strand, while $a_1$
refers to the segment at the 3' end of the strand.
Segments with different labels may share
the same index, as in $[a_0 b_0 a_1]$
Omitting an index in the case of duplicate
labels leads to ambiguity
and so is considered a syntax error, as in $[x y x]$.
Likewise, repeating the index of segments
that share the same label is considered
a syntax error, as in $[x_0 y x_0]$.

For brevity, we sometimes use abstraction.
The simplest abstraction uses standard
ellipses to denote elision, e.g.,
$[a_0 b_0 a_1 b_1 \dots a_{99} b_{99} a_{100} b_{100}]$.
Ellipses may also be used to elide irrelevant
structure, such as focusing on two segments
amidst a larger complex $[\dots a \overline a \dots ]$.
If this is the case, then we can 
substitute a variable or expression, such
as $[a_0 b_0 a_1 b_1 \dots a_{i} b_{i}
a_{i+1} b_{i+1} \dots a_{100} b_{100} ]$.

By choosing appropriate sequences, a designer
can reduce extraneous complement symmetries
among sequences to something like two or three base pairs.
Because the hybridizing affinity of long
\index{hybridizing affinity}
matches vastly outweighs the hybridizing
affinity of short matches, 
matches below a certain threshold length are ignored.
We assume that either two segments will
hybridize along their entire length in the
case that their labels are complementary,
or two segments will effectively have
zero base-base interaction if their labels are not complementary.
A machine for which this property holds true
for every pair of labels is said to have a \textit{consistent} labeling.
\index{consistent labeling}%

Labels can be split or merged
\index{labels, split and merge}%
in order to preserve consistency. 
For example, consider one machine containing
the label $a$ and another machine containing
the label $b$, each with a consistent
labeling when considered alone. Suppose the
first half of $a$ serves as the complement to the first half of $b$.
In this case, we split the labels
yielding $a = e c$ and $b = \overline e
d$. Then we replace all occurrences of $a$ and $b$ appropriately.
Likewise, if we find that two labels,
say $g$ and $h$, are always ligated
as $\dots g h \dots$ and that the same holds true for their 
complements as $\dots \overline h \overline g \dots$,
then the two labels can be merged and we can say that $k = g h$.
Note that due to the anti-parallel nature
of hybridizing, the complement of concatenated
labels are the commutated complements,
i.e., $\overline k = \overline{g h} = \overline h \overline g$.



\subsection{Hybridization}

When one segment is hybridized to another, each will indicate
its partner through a superscript.
\index{hybridization, indication of partners}%
\index{notation: superscript indicates hybridization partners}%
So, for example, a complex referred to
as a \textit{hairpin} could be represented
as $[ \overline a_0^{a_0} b_0 a_0^{\overline a_0} t_0]$.
\index{hairpin}%
Because only complementary strands are able
to hybridize, it is unnecessary to repeat
the label of the hybridized partner, so
simply superscripting the partner's index
will suffice $[ \overline a_0^0 b_0 a_0^0 t_0 ]$.
If the hybridized partner does not have
an index---in the case where it is the
only instance of that particular label---then
an asterisk will serve as a placeholder,
thus $[ \overline a^* b a^* t]$ is equivalent to the hairpin above.
%
\begin{figure}[hbt]
	\centering
	\includegraphics{ch2-fig04.eps}
	\caption[A hairpin]{The hairpin $[ \overline a^* b a^* t]$ }
	\label{fig:hairpin}
\end{figure}

We use a vertical bar or a pipe character to demarcate different strands.
\index{notation: vertical bar indicates unconnected strands}%
A simple example of a stretch
of duplex DNA consisting of two complementary
strands hybridized together, as in Figure~\ref{fig:aA_duplex},
would be $[ a_0^0 | \overline a_0^0 ]$ or $[
a^* | \overline a^* ]$ using the shorthand.
The vertical bar thus implies a plurality of strands.
In the case of Figure~\ref{fig:hairpin},
we have a single unbroken strand, and
thus the vertical bar notation does not apply.
By contrast, because the complex in figure~\ref{fig:aA_duplex}
contains two distinct strands, we need
a vertical bar to demarcate the strand boundaries.
Note that because the vertical bars are
merely used as delimiters, the particular
order in which the strands are listed
is arbitrary: e.g., $[ a^* | \overline a^* ] = [ \overline a^* | a^* ]$.
%
\begin{figure}[hbt]
	\centering
	\includegraphics{ch2-fig05.eps}
	\caption[A complex with multiple strands]{
A complex consisting of multiple non-continuous strands, such as
$[ a^* | \overline a^* ]$, demonstrates the
use of a vertical bar to demarcate separate strands.
Note that the order in which the strands are listed
is immaterial. So, the notation
$[ \overline a^* | a^* ]$ also describes the complex above.}
	\label{fig:aA_duplex}
\end{figure}

Using this notation,
we can enumerate
the various syntax errors which do \textit{not}
constitute a valid strand.
In the following examples the superscript of $x_0$ is invalid:
\begin{itemize}
	\item no complementary segment is indexed
by the superscript, such as in $[ x_0^* ]$ or $[ x_0^1 \overline x_0 ]$
	\item multiple complementary segments
are indexed by the superscript, such as in $[ \overline x_0 x_0^* \overline x_1 ]$
	\item the complementary segment indexed
by the superscript does not itself have a superscript $ [x_0^* \overline x ]$;
	\item the complementary segment indexed
by the superscript  $[ x_0^* \overline x_0^1 x_1^0 ]$.
\end{itemize}

Note that, as currently specified, this
notation allows for multiple disjoint
and non-connected components to be listed as a single complex.
For example, $[ a^* b \overline a^* t | e^*
| \overline e^* ]$ is a syntactically legal
construction. However, it consists of two
entirely separable components, namely
the hairpin $[ a^* b \overline a^* t ]$ and the duplex $[ e^* | \overline e^* ]$.
Thus, a valid \textit{component} 
\index{component,: defined}%
is defined as a collection of strands that cannot 
be further decomposed into a legal
construction without cutting strands or disrupting hybridizations.
A \textit{complex}, in general, 
denotes any set of valid components, and
can be listed using standard set notation.
\index{complex, defined}%
For example, we might say $\Omega = \{ [ a^*
b \overline a^* t ] , [ e^* | \overline e^* ] \}$,
where $\Omega$ denotes a complex consisting of multiple components.
When representing a simple case such as
one or two components and a single complex,
we use a simple comma-separated list. 

For the purpose of processing by computer, we specify
a plaintext (ASCII-friendly) version
of this notation, in which we avoid all use of 
bars and subscripts. 
\index{ASCII friendly notation}%
\index{plaintext notation}%
In this instance, labels are always alphabetic
characters, and complements are denoted by
changing case; so $[ a b \overline a ]$ would become \verb$[a b A]$.
Segment indices are simply appended, rather
than subscripted, so $[ x_0 y x_1 ]$ would become \verb$[x0 y x1]$.
In the case of a variable or expression,
the index is enclosed in curly braces,
so that $[ \dots x_i \dots ]$ would become \verb$[... x{i} ...]$
If there are more labels than alphabetic
characters, labels can be multiple characters
long. Because this can sometimes lead to
confusion, one must 
separate labels with whitespace. For example,
$[ \alpha \beta \overline \alpha ]$ might become \verb$[alpha beta ALPHA]$.
In order to denote hybridization without support
for subscripts, one simply appends a caret
and then the index of the hybridized partner;
so the hairpin $[ a^* b \overline a^* t ]$
would become \verb$[a^* b A^* t]$ or \verb$[a0^0 b0 A0^0 t0]$, 
depending on the level of verbosity desired.

\begin{table}[hbt]
\caption{A summary of the notation syntax}
\label{tab:syntax}
\plaincenterline{\mytable
\begin{tabular}{ccp{3.2in}}
{\cb notation} &{\cb ascii} &{\cb description}
\\ 
$a$ & \texttt{a} & a label 
\\
\cy $\overline a$ &\cy \texttt{A} &\cy the complement of label $a$ 
\\
$\overline a_2$ & \texttt{A2} &  segment indices
distinguish multiple label instances
\\
\cy $a^2$ &\cy \texttt{a\^2} &\cy $a = $\texttt{a}
is hybridized to the segment $\overline a_2 = $\texttt{A2} 
\\
$\overline a_2^*$ & \texttt{A2\^*} & $\overline a_2
= \texttt{A2}$ is hybridized to the only instance of $a = $\texttt{a} 
\\
\cy $a_{i+1}$ &\cy \texttt{a{i+1}} &\cy abstraction
of numerals by arbitrary expressions 
\\
$\dots$ & \texttt{...} & arbitrary segments
and strands, or continuation 
\\
\cy $\dots a b \dots$ &\cy \texttt{... a b ...}
&\cy the 3' end of $a$ is ligated to the 5' end of $b$ 
\\
$a \dots | \dots b$ & \texttt{a ... | ... b} 
& $a$ and $b$ are on different strands 
\\
$\cy(a \dots b)$ &\cy \texttt{(a ... b)} &\cy the
3' end of $b$ is ligated to the 5' end of $a$ to form a loop
\\
$[ a^2 \overline a_2^*]$ & \texttt{[a\^2 A2\^*]}
& brackets enclose a complete component or complex 
\end{tabular}
\emytable}
\end{table}


{\em Tondo: The above doesn't look right in that the hats
are not where they should be. Please see the original below.}


\begin{table}
	\centering
	\begin{tabular}{|c|c| p{.6\textwidth}|}
		\hline
		notation & ascii & description \\ \hline
		$a$ & \verb$a$ & a label \\
		$\overline a$ & \verb$A$ & the complement of label $a$ \\
		$\overline a_2$ & \verb$A2$ &  segment indices distinguish multiple label instances\\
		$a^2$ & \verb$a^2$ & $a = \verb'a'$ is hybridized to the segment $\overline a_2 = \verb'A2'$ \\
		$\overline a_2^*$ & \verb$A2^*$ & $\overline a_2 = \verb'A2'$ is hybridized to the only instance of $a = \verb'a'$ \\
		$a_{i+1}$ & \verb'a{i+1}' & abstraction of numerals by arbitrary expressions \\
		$\dots$ & \verb'...' & arbitrary segments and strands, or continuation \\
		$\dots a b \dots$ & \verb'... a b ...' & the 3' end of $a$ is ligated to the 5' end of $b$ \\
		$a \dots | \dots b$ & \verb'a ... | ... b' & $a$ and $b$ are on different strands \\
		$(a \dots b)$ & \verb'(a ... b)' & the 3' end of $b$ is ligated to the 5' end of $a$ to form a loop\\
		$[ a^2 \overline a_2^*]$ & \verb'[a^2 A2^*]' & brackets enclose a complete component or complex \\
		\hline
	\end{tabular}
	\caption{A summary of the notation syntax}
	\label{tab:syntax}
\end{table}




\subsection{Nodes}

You can think of the overall structure of the DNA complex
as a formal graph structure
consisting of nodes and edges.
\index{nodes and edges}%
Edges will consist of either
a directed single segment or an undirected
duplex pair of hybridized segments.
Nodes will be junctions where such
edges meet; they will necessarily come
in distinct types, based on the 5'--3'
connectivity of the segments involved in such edges.
Note that the ``ordering'' of the edges
around a node matters; for this reason,
the graph structure of nodes and edges
alone is not sufficient to capture the full topology of such a DNA structure,
as will be discussed in Chapter~\ref{ch03}.
The graph characterization
is enough for our clocked stored program DNA computer
and for the other machines we discuss, however.
{\em Tondo: The rightmost heading type c should be type d in the figure.}
%
\begin{figure}[hbt]
	\centering
	\includegraphics{ch2-fig06.eps}
\caption[The various types of nodes]{A chart of the various types of nodes.
Each one represents a possible way in which strands can meet at a junction. }
\label{fig:nodes}
\end{figure}


\section{Transitions}

Because we want to model dynamic machines,
we will formulate changes or transitions in terms of the representation
from the previous section.
\index{dynamic machines}%
\index{transition}%
In doing so, we ignore
small perturbations of a complex, as they
do not affect the overall topology of the DNA structure.
We consider only those changes that affect
the hybridization or ligation of segments.

\subsection{Spontaneous Transitions}


There are three basic transitions that
will occur spontaneously in solution,
provided the proper temperature and solvent environment is present. 
\index{transition, spontaneous}%

\subsubsection{Hybridization}
Hybridization transitions characterize the
simple hybridization of two unpaired single
stranded segments when those segments are at least partly complementary.
Consider the case where we have the segments $a_i$ and $\overline a_j$.
The transition $A_{ a_i , \overline a_j }$
hybridizes these two segments to one another.
\index{hybridize transition}%

In our representation, this entails superscripting
$a_i$ with $j$ to make $a_i^j$
and transforming $\overline a_j$ into $\overline a_j^i$.
Formally then, if we have un-hybridized
segments $a_i$ and $\overline a_j$ in some complex $\Omega_0$, then we can define:
\begin{equation}
	A_{ a_i , \overline a_j } : \Omega_0 \rightarrow \Omega_1
	\label{eq:hybridize_def}
\end{equation}

In the above, $A_{a_i,\overline a_j}(\Omega_0)
= \Omega_1$ is the following mapping:
\begin{equation}
	[ \dots a_i \dots \overline a_j \dots ] \mapsto
[ \dots a_i^j \dots \overline a_j^i \dots ]
	\label{eq:hybridize_map}
\end{equation}

The two segments involved may be anywhere within the complex.
Hybridization may involve segments in two different
components, in which case these components
are merged into a single component.
For example, $A_{a,\overline a}([a],[\overline a]) = [a^*|\overline a^*]$.
%
\begin{figure}[hbt]
	\centering
	\includegraphics{ch2-fig07.eps}
\caption[An example of the hybridize transition]{An
example of the hybridize transition $A_{a,\overline a}$  }
	\label{fig:hybridize}
\end{figure}


\subsubsection{Displace}

Displace is called a branch migration.
\index{displace}%
\index{branch migration}%
The \textit{displace} transition replaces
one single stranded segment with another
of the same label already in an hybridized pair.
Consider the single segment
$a_i$ along with the duplex pair $a_j^k$ and $\overline a_k^j$.
The transition $D_{a_i , a_j }$ will then
cause $a_i$ to ``displace'' $a_j$, taking
its place in the duplex pairing with $\overline
a_k$ and leaving $a_j$ un-hybridized.
In the notation, this entails adding a
superscript to $a_i$ to yield $a_i^k$,
removing the superscript from $a_j^k$
to yield $a_j$, and replacing the superscript
of $\overline a_k^j$ to yield $\overline a_k^i$.
Thus, if we have the segments (along with
hybridizations)  $a_i$, $a_j^k$, and $\overline
a_k^j$ in some complex $\Omega_0$, then we can define:
\begin{equation}
	D_{a_i,a_j} : \Omega_0 \rightarrow \Omega_1
	\label{eq:displace_def}
\end{equation}

In the above, $D_{a_i,a_j}(\Omega_0) = \Omega_1$ is the following mapping:
\begin{equation}
	[\dots a_i \dots a_j^k \dots \overline a_k^j
\dots] \mapsto [\dots a_i^k \dots a_j \dots \overline a_k^i \dots]
	\label{eq:displace_map}
\end{equation}

By convention, the segment that is initially
un-hybridized is always listed as the first argument.
Also, one needs to specify only two segments,
as the third segment---in this case $\overline
a_k$---can be determined from the subscript of the second argument.
%
\begin{figure}[hbt]
	\centering
	\includegraphics[width=\textwidth]{ch2-fig08.eps}
\caption[An example of the displace transition]{An
example of the displace transition $D_{a_1,a_0}$.
This is a non-separating displace and
is thus reversible by applying $D_{a_0,a_1}$ to the resulting complex.}
	\label{fig:displace}
\end{figure}

A displace transition is \textit{node-initiated},
\index{node-initiated}%
when the single segment must
meet the duplex segments at some node.
that node is called the \textit{initiating
node}; the node at the opposite end of
\index{initiating node}%
\index{terminating node}%
the duplex segments is called the \textit{terminating node}.
When the terminating
node is anything but type a (see Figure~\ref{fig:nodes}),
the displace may cause the terminating
node to be transformed into two distinct nodes. This
is referred to as a \textit{separating} transition.
\index{separating transition}%

In the non-separating case, the transition
can be reversed by swapping arguments.
That is, applying $D_{a_i,a_j}$ first and then $D_{a_j,a_i}$
immediately afterwards causes 
the complex to return to its original configuration.
In the case of a separating transition,
a displace transition sometimes results in two distinct components.
For example, in the case of $D_{ a_0 ,
a_1 }([a_0 \overline a_1 | a_1^*])$ the complex
has a 2-valent initiating node of type
c and a 1-valent terminating node of type b.
This separating transition
results in the disjoint components $[a_0^* \overline a^0]$ and $[a_1]$.
The initiating node has become a 1-valent
type a node, and the terminating node
has separated to become a 1-valent node
of type b and a 1-valent node of type c.

	

\subsubsection{Exchange}

This is sometimes called a duplex branch migration.
\index{duplex branch migration}%
\index{exchange}%
The \textit{exchange} transition takes
two duplex segment pairs of the same label and exchanges their partners.
Consider that we have the duplex pair
$a_i^j$ and $\overline a_j^i$ along with the
duplex pair $a_r^s$ and $\overline a_s^r$.
The transition $E_{a_i,a_r}$ will then
cause $a_i$ and $a_r$ to effectively trade hybridizing partners with
one another.
The ligation does not change however.
This manifests in the notation as swapping
the superscripts of $a_i^j$ and $a_r^s$
to yield $a_i^s$ and $a_r^j$, and likewise
swapping the superscripts of $\overline a_j^i$
and $\overline a_s^r$ to yield $\overline a_j^r$ and $\overline a_s^i$.
For example, if we have $a_i^j$, $\overline a_j^i$,
$a_r^s$, and $\overline a_s^r$ in some complex $\Omega_0$, we define

\begin{equation}
	E_{a_i,a_r} : \Omega_0 \rightarrow  \Omega_1
	\label{eq:exchange_def}
\end{equation}

where $E_{a_i,a_r}(\Omega_0) = \Omega_1$ is the mapping

\begin{equation}
	[ \dots a_i^j \dots a_r^s \dots \overline
a_j^i \dots \overline a_s^r \dots] \mapsto
[ \dots a_i^s \dots a_r^j \dots \overline a_j^r \dots \overline a_s^i \dots] 
	\label{eq:exchange_map}
\end{equation}

For the sake of convention and consistency
with displace, the two segments specified should have identical labels.
Also note the various symmetries of the operation. 
For $a_i$ hybridized to $\overline a_j$ and $a_r$
hybridized to $\overline a_s$, we have

\begin{equation}
	E_{a_i,a_r} = E_{a_r,a_i} = E_{\overline a_j,\overline
a_s} = E_{\overline a_s,\overline a_j}
	\label{eq:exchange_sym}
\end{equation}

Like displace,
an exchange transition is \textit{node-initiated}.
\index{node-initiated}%
However, unlike displace, there are two
terminating nodes. They are at the ends of the
duplex segments opposite the initiating node.
Whether or not an exchange is separating
now depends on the types of both terminating
nodes. If either is type a, then it is a non-separating transition.
As with displace, the transition is reversible
in the non-separating case. 
Any of its symmetrical forms serve as an inverse.
So, applying $E_{a_i,a_r}$ first and then $E_{a_i,a_r}$ second
results in no change to the complex.
An example of the non-separating case
\index{non-separating}%
is shown in figure~\ref{fig:exchange}.
An example of the separating case would
be $E_{a_0,a_1}([a_0^0 \overline a_1^1|a_1^1
\overline a_0^0]) = [a_0^1 \overline a_1^0],[a_1^0 \overline a_0^1]$
in which two cross-hybridized strands separate into two separate
continuous self-hybridized strands.
%
\begin{figure}[hbt]
	\centering
	\includegraphics[width=\textwidth]{ch2-fig09.eps}
\caption[An example of the exchange transition]{An
example of the exchange transition $exchange_{a_1,a_0}$;
this is a non-separating exchange and is thus reversible.
{\em Editor: step 1 is missing a strand. All one sees is the downward
pointing arrowhead but the strand should start opposite the arrow
on the upper left, go above the $\overline a 0$ and then
go vertically down to the arrowhead just above the words "step 1"}
}
	\label{fig:exchange}
\end{figure}



\subsection{Manual Transitions}

There also are several transitions that
do not occur spontaneously but rather require
either human intervention by way of lab
protocol, the actions of proteins, or by other mechanisms.

\subsubsection{Pour and Filter}

These transitions are effectively inverses of one another.
The pour transition consists of
adding components to a complex to allow for interaction.
An example of this might be $pour_{[b]}([a]) = [a],[b]$.
In essence, pour is a simple multiset union.
\index{pour}%

Filter is the inverse of pour, removing
\index{filter}%
specified components from a complex.
So thus $filter_{[b]}([a],[b]) = [a]$.
Thus, filter is a set partitioning.

In general, pour is straightforward
to apply physically, as one
can simply pour a vessel full of one complex
into a vessel full of another complex.
Filter on the other hand has no simple realization.
One may filter
on weight by use of a centrifuge, or by
size by performing a gel-electrophoresis
run, or by selecting on certain sequences by use of protein binding.
Occasionally these transitions do not
correspond to actual laboratory operations
or even physical changes, but merely serve as a notational expedient.
For example, certain ``waste'' components
may no longer be able to interact in any
transitions 
such as the component $[a_*|\overline a_*]$.
Because such a duplex strand is stable, it does not affect further
operation of the machine and therefore may be ignored.
\index{waste as complementary duplex}%


\subsubsection{Cleave and Ligate}

These transitions correspond to joining
or breaking covalent bonds along the DNA
backbone. These are performed by proteins,
such as DNA ligase, FokI, and others.
\index{cleave}%
\index{ligation}%
These transitions manifest in the notation
as the addition or removal of vertical pipes.
For example, $cleave_{a_i,b_j}(\dots a_i b_j ) = \dots a_i | b_j \dots $.
In the case of loop strands, the segments
to be cleaved should first be rotated
to be adjacent to the parenthesis, so
that $|( \dots a_i b_j \dots )|$ should
be first rewritten as $|(b_j \dots a_i)|$.
At this point, we have $cleave_{a_i, b_j}:
|(b_j \dots a_i)| \mapsto |b_j \dots a_i|$
Remember that the arguments are always listed in a 5' to 3' order.

The ligate transition joins an open 3' endpoint and an open 5' endpoint.
Notationally this manifests as the simple
deletion of a vertical pipe. Physically, this corresponds 
to the concatenation of two strands.
Two segments can be ligated provided one
has an open 3' endpoint and the
other has an open 5' endpoint; labeling is irrelevant.
Strands should first be re-ordered to
place the segments to be ligated adjacent
to one another.
So for example, $ \dots a_i | \dots |
b_j \dots $ should become $ \dots a_i | b_j \dots $
Thus, in general we have $ligate_{a_i,b_j}: 
\dots a_i | b_j \dots \mapsto \dots a_i b_j \dots $

In the case that the segments to be ligated
are the endpoints of the same strand,
such as $|a_i \dots b_j|$, then the application
of ligate creates a loop strand and manifests
as the addition of parentheses as $ligate_{a_i
, b_j}: |a_i \dots b_j| \mapsto |(a_i \dots b_j)|$.
As with cleave, the arguments are always listed in 5' to 3' order.




\subsection{Syntactic}

Although not true transitions in the physical
sense, these transitions allow for adjusting
syntax without changing the underlying structure of the complex.
In general, syntactic transitions 
may simply be performed in the notation.
The following are all the syntactical transitions:

\begin{itemize}
	\item Rotate the listing of segments in a loop strand. 
	\item Rearrange the listing order of strands in a component.
	\item Add a numeral to the only occurrence
of a label, and replacing any asterisk
that may refer to that segment with that numeral.
	\item Omit a numeral from the only
occurrence of a label, then replace any
subscripted numeral that may refer to that segment with an asterisk.
	\item Merge two labels as described in the Labeling subsection
at the beginning of this chapter.
	\item Split two labels as described in the Labeling subsection.
	\item Rename all occurrences of a label
to some unused label name.
\end{itemize}


\section{Dynamic Behavior}

With the basic transitions formalized,
we can now describe the overall behavior
of a DNA nanomachine system  as a kind of state machine.
Each state is represented by a particular
complex---equivalently, a string or set
of strings---and state transitions are
drawn from the transitions described above.
In general, because there may
be multiple potential transitions for
a given complex, the state transitions
may constitute a non-deterministic state machine.

\subsection{Stabilization}

In solution, DNA machines
naturally progress through available spontaneous
transitions in a process we call \textit{stabilization}.
\index{stabilization: precedence}%
Not all transitions are equally favored,
however; some are more likely to occur,
or occur more quickly than others.
Node-initiated transitions (hybridize, displace, and exchange) 
will occur more easily than 
non-node-initiated transitions.
Among node-initiated transitions, hybridizations
occur rapidly and are energetically favorable. 
So, hybridizations have the highest precedence.
Both displace and exchange transitions
progress along segments from the initiating
node in a random walk fashion, moving
either forwards or backwards one base
pair at a time. This makes them slower than a hybridization.
Because, at each step, a displace must only
break and make one base pair bond, whereas
an exchange must make and break two, a
displace transition will generally take precedence over an exchange.
Except in cases of extremely high concentrations
of DNA, intra-component transitions occur more frequently 
than inter-component transitions.

Thus, we can establish a rough (nested)
precedence order for spontaneous transitions.
Keep in mind that the deeper nested transitions
are more similar in precedence to one
another; in many cases, for example, it
makes sense to treat all node-initiated
transitions as having equal precedence.

\begin{enumerate}
	\item intra-component transitions:
		\begin{enumerate}
			\item node-initiated transitions:
				\begin{enumerate}
					\item hybridize
					\item displace
					\item exchange
				\end{enumerate}
			\item disjoint hybridize
		\end{enumerate}
	\item inter-component disjoint hybridize
\end{enumerate}

With such a precedence established, the
process of stabilization can be simulated
by producing a \textit{stabilization diagram},
which is a state machine diagram recording
\index{state machine diagram}%
all component states and potential transitions.
First, each component of the machine in
question is recorded as if it were a distinct state.
Then, each component in this set is examined
to determine if any potential transitions (from high precedence
to low) are available.
For inter-component
transitions, all components in the current
iteration must be considered for possible interaction.
The diagram is then expanded to include
any new components that result from these
new transitions, as well as adding in the transitions themselves.

This process is continued in successive
stages until there are no longer any new states being introduced.
Out of the resulting components, those
that have no available transitions will
be referred to as \textit{stable}.
\index{stable state}%
There may also be cycles of states in
which each state has an available transition,
but the transitions stay within that set
of states without preferring any one over the other.
The states which make up such a cycle
will be referred to as \textit{semistable}.
While the introduction of a
precedence ordering diminishes the
non-determinism to some extent, there
can be cases which are inherently non-deterministic.
%
\begin{figure}[hbt]
	\centering
	\includegraphics{ch2-fig10.eps}
\caption[A state diagram of the stabilization
process]{A state diagram for the stabilization
of a particular strand, in this case $[ a_0 \overline a_0 a_1 \overline a_1 ]$.
Note that the final two states are semi-stable. The hats in the 
figure are represented as carets.}
	\label{fig:stabilize_semi}
\end{figure}	

\subsection{Stoichiometry}

So far, we have ignored the particular concentrations
of components.
In many or perhaps even most cases, while
there may be multiple available transitions
at any given iteration, the transitions
do not directly compete with one another.
It does not matter in which order the transitions
in question are performed, because the resulting
complex is the same. In effect, the transitions are commutative.
By contrast, there are many cases in which
transitions do compete,  i.e., do not commute,
and one set of transitions can lead to a different final state than
another.

In those cases,
concentrations can affect the operation of the machine.
Thus, a state having a non-deterministic outcome when concentrations
are unknown may turn into a state having a deterministic
outcome when the stoichiometry---ratios
between amount of transitioned components--- is controlled.
\index{stoichiometry}%
For example, for many transitions that
involve multiple components---such as
an inter-component hybridization---one of the
components may serve as a limiting factor if the quantities are unequal.
Determining the correct ratios between components requires a model.

Here is a naive model that is likely to be approximately correct
in the large numbers world of a DNA solution.
First, let $Q_i$ represent the numerical quantity of the $i$th component.
In the case of intra-component hybridizations,
at a particular iteration of the stabilization
process, suppose there are $n_i$ distinct
transitions involving the $i$th component.
Then for a particular transition involving the $i$th component, 
{\em assume} the transition will occur
on the quantity $\frac{Q_i}{n_i}$ of that component.
For inter-component transitions, consider
the combinatorial problem of drawing two
components at random from a bag of quantities;
this will be roughly the probability that they interact in solution.
Thus, for a transition involving the $i$th
component and the $j$th component, where
there are a total of $n_{ij}$ distinct
transitions involving these two segments,
{\em assume} the transition will be performed
on the quantity $\frac{Q_i Q_j}{n_{ij}
\sum_{\forall k} Q_k}$ taken from each of the two components.


This ``perfect mixing'' model may leave some components unchanged.
At each iteration of this process, say
$\Delta Q_i$ is the change in quantity
of the $i$th component from the previous iteration to the current.
If component $i$ did not exist in
the previous iteration, $\Delta Q_i$ will simply
be the quantity of the component.
Now we can introduce a threshold quantity
$\epsilon$ in order to cut the tail off
such asymptotes and make the stabilization calculation terminate.
Any quantity below this threshold can
effectively be ignored. 
Thus, the stabilization process will repeatedly
progress through the transition precedence
levels, distributing quantities in ratios
determined by the formulas above, until
$\Delta Q_i < \epsilon$ for all components.
In collaboration with us, Christofer Hedbrandh has developed
a stabilization algorithm based on this
formula that takes stoichiometry into account.
His software is 
implemented in python\citep{christofer}.


\subsection{User-level State Diagram}

Once the stabilized state is determined,
the stabilization process can be thought of as a single step.
Thus, we might think of stabilization as a
\textit{subroutine} and treat it as
\index{subroutine}%
a single function applied to a complex.
Subroutines may be used as state transitions
to simplify the state diagram.
A user can conceptualize
the system as a state diagram from stabilized state to stabilized state.
In such a state diagram, the transitions
will consist of the combined subroutine
of a manual transition---such as pour
or filter---immediately followed by stabilize.

In practice, most DNA nanomachines or
motifs consist of a single ``main'' component
\index{main component}%
that progresses through several states.
The dynamic behavior of this component
is fueled by inputs that generally consist of simple strands or hairpins.
As the main component progresses through these
states, it produces ``waste'' components that don't interact
further with the main component and therefore can be ignored.

\clearpage

