
\blankpage

\chapter{A Topological Description of DNA Computing}
\label{ch03}

This chapter gives an alternate topological description of
the statics and dynamics of our system.
If you are a topologically-inclined thinker, then you might
find this chapter very helpful.
Otherwise, you can skip
the chapter without loss of continuity.

\section{As a Cell Complex}

\subsection{State}

From a topological standpoint, we might
choose to view a DNA complex as a cell/CW
complex, or henceforth simply a \textit{complex}.
\index{cell complex}%
A complex captures the topology of an
object by breaking it up into some finite
number of \textit{$n$-cells}---an $n$-dimensional
\index{n-cells}%
object homeomorphic to an open ball---and
recording the precise manner in which
these cells are attached to one another.
Additionally, we may also specify one
of two \textit{orientations} for a cell.
\index{orientations}%

A 0-cell will correspond to the sugar-phosphate
bond linking together nucleotides along
the DNA backbone; we can view this as
a 0-dimensional object, merely occurring at a single point.
Orientation allows us to capture the 3'
or 5' nature of these bonds. We can consider
the point of attachment at the 5' end
to be ($-$) oriented and the point of
attachment at the 3' end to be ($+$) oriented.

A 1-cell then corresponds to a nucleotide,
which we can view as a line segment connecting
two 0-cells; the corresponding line segment
will be oriented in the standard 5' to 3' direction.
This allows us to capture the 5' / 3'
nature of the DNA backbone by allowing
two 1-cells to be attached to one another.
The attachment consists of
identifying or gluing together
two oppositely oriented 0-cells into a
single, un-oriented 0-cell. 
As a result, the orientation of the 1-cells will remain
consistent across the attachment.

A 2-cell serves to represent the hydrogen
bond between a pair of bases and manifests
as a ribbon or a sheet between the two
line segments; much as with the 1-cells,
here the orientation is induced by the
1-cells, or nucleotides, running along either side.
We might demonstrate this orientation
in a diagram by coloring white the side
from which it appears that the boundary
1-cells are oriented counter-clockwise,
and coloring black the side from which
it appears that the boundary 1-cells are oriented clockwise.
The way in which
1-cells are attached determines whether the
orientation coloring remains consistent along the length of duplex DNA.
From a formal standpoint we would also
need two additional 1-cells ``capping''
the ribbon at either end, naturally extending
to the process of ``gluing'' oppositely
oriented capping 1-cells in order to attach
2-cells; we will come back to these later

An \textit{edge} will either be directed
and consist of a single un-hybridized 1-cell,
which we might refer to as a \textit{simplex
edge}, or it will be undirected and consist
\index{simplex edge}%
of a pair of hybridized 1-cells, which we
might refer to as a \textit{duplex edge};
\index{duplex edge}%
in both cases, the edge is thought of
as running parallel to the backbones.

A \textit{node} will be a generalization
of the Holliday junction, consisting of
\index{Holliday junction}%
some combination of simplex and duplex
edges meeting along a short line segment or loop.
As duplex edges will connect to one another
at a node via the ``corners'' of each
ribbon-like 2-cell, the node will take
roughly the form of a short loop or line
segment with these ``ribbons'' hanging off.
If we are looking down the ``axis'' of
a node, the 2-cells will have a consistent
orientation, such that the ``white side''
of every 2-cell faces clockwise,
or every 2-cell faces counterclockwise.
This is used to determine a consistent
ordering in which to list the edges of
a node. If we are to ``flatten'' the node
out with edges pointing downwards and
the ``white side'' of every 2-cell facing
us, then the edges will be listed from left to right.
In terms of the ``cap'' 1-cells mentioned
previously, each node would be a contiguous
chain of such cap 1-cells; the orientation
of these cap 1-cells determines the ordering
of the canonical list of edges.

\subsection{Transitions}

In a formal sense, each state is a homotopy
\index{homotopy}%
equivalence class of embeddings.
Transitions will be distinct topological
events, corresponding to adding, deleting,
separating, or joining together various cells.
We will consider three basic types of
transitions: Hybridize, Displace, and Exchange.
These will be much like the Riedermeister
\index{Riedermeister}%
moves of knot theory. However, unlike
Riedermeister moves, there is a directionality
to these transitions. They will operate
on a 3-dimensional embedding, rather than a 2-dimensional projection.
All transitions will consist of topological
surgery, which replaces the interior of
a small bounding sphere containing a specific
arrangement of cells, with another specific
arrangement of cells, while keeping the
surface or ``shell'' of this bounding sphere fixed.
In general, for the three basic transition
types, the bounding sphere will contain
some number of roughly parallel (or anti-parallel)
1-cells, with their bounding 0-cells lying
on the surface of the sphere; these 1-cells
remain more-or-less fixed throughout the
transition, while various additions and
deletions are made to the 2-cells within the bounding sphere.
Attention must also be paid to correct
label inverse behavior, and all hybridizations
in both the start and end state must be ``legal'' in this sense.

The \textit{Hybridize} transition represents
a simple hybridization of unpaired nucleotides.
The initial state of the bounding sphere
will contain two 1-cells corresponding
to an un-hybridized pair of matching nucleotides:
one is oriented ``upwards'' which we might
refer to as $a$, and one is oriented ``downwards''
which we might refer to as $b$.
The end state of the bounding sphere will
contain the same two 1-cells, now with
the addition of a 2-cell between $a$ and $b$.
The transition is naturally unidirectional,
because hybridized base pairs typically do not spontaneously separate.

The \textit{Displace} transition represents
the displacement of one hybridized nucleotide by an un-hybridized nucleotide.
The initial state of the bounding sphere
will contain three 1-cells with one oriented
``upwards,'' which we might refer to as
$a$, and two oriented ``downwards,'' which
we might refer to as $b_1$ and $b_2$.
Initially, there will be a 2-cell between
$a$ and $b_1$. The end state is obtained
by the deletion of this initial 2-cell
and the addition of another between $a$ and $b_2$.
Because the initial state and the end state
are related by symmetry, this transition will naturally be bidirectional.
However, we might also form an equivalent
formulation by treating the different
``chiralities'' of such a transition as
distinct unidirectional transitions; this
is analogous to the case of Reidermeister
moves, where we might treat the various
symmetries as distinct from one another.

The \textit{Exchange} transition represents
the swapping of nucleotides between two
hybridized pairs; this transition provides
for the mobility of a classical Holliday junction.  
The initial state will have four 1-cells
with two oriented ``upwards,'' which we
might refer to as $a_1$ and $a_2$, and
two oriented ``downwards,'' which we might
refer to as $b_1$ and $a_2$. These orientations
alternate as one travels (roughly) around
the equator of the sphere. Listing
them counterclockwise, we might have $a_1$, $b_1$, $a_2$, $b_2$.
There will also be two 2-cells, one between
$a_1$ and $b_1$ and another between $a_2$ and $b_2$.
The end state is obtained by the deletion
of these 2-cells and the addition of two
other 2-cells, one between $a_1$ and $b_2$
and another between $a_2$ and $b_1$.
Likewise as with Displace, the initial
state and end state are related by symmetry,
making the transition a bidirectional
one; and we might also treat the various
chiralities as distinct unidirectional transitions. 


We might also consider transitions such
as \textit{Pour} and \textit{Filter} that
add or subtract components to the complex.
Viewed as straightforward disjoint
union and intersection operations, these
correspond to pouring two solutions together
or mechanically filtering out particulates
and should be treated as unidirectional transitions.

\clearpage

