
\chapter{Introduction}
\label{ch01}


% {\em Storing Clocked Programs Inside DNA: a simplifying 
% framework for nanocomputing}


Imagine the world before electronic computers.
If an enterprise needed to figure out, say, a scheduling problem,
it would have to call an expert who might come trotting along
with a calculator.
The expert would be needed because he or she would know the procedures
to use.
Nowadays, the enterprise can simply download scheduling software,
store the software inside an electronic computer and execute it.

The current world of DNA computing is much like the calculator era.
Researchers develop a sophisticated collection of DNA operations
(analogous to designing and installing
logarithms and trigonometric functions inside calculators or slide
rules).
This is useful and vital work.
But if an operation requires
N different strands, then the inventor must ship N vials containing those
different strands 
to a site that is going to perform that operation.
Moreover, the strands must be introduced
into the solution  in a specific order, so it might help
to send an expert along just in case.

This book shows a way to construct clocked DNA programs that can be shipped
from one site to another, much in the same way that
scheduling software can be shipped around the world.
An inventor (DNA software
developer) will be able to create a program consisting of
millions of DNA ``sculptures''
and then send them to labs all over
the world.
The lab would have to pour two ``clock'' strands
called ``tick'' and ``tock'' in an alternating
fashion to run the DNA program.

We begin by defining a language that can describe states of a set of
strands of DNA.
Our description is graph theoretic except in Chapter~\ref{ch03}
when it is topological.
(The topological description captures the order of strands around
each junction, whereas the graph-theoretic
description does not, but that 
ordering is unnecessary for our clocked stored programs.)
We then use the language to describe transitions to move from
one state to another.
This gives us the ability to recapitulate
all DNA machines that we know of.
Finally, we describe a clocking mechanism that allows us to store
clocked programs inside DNA that 
can mimic any machine in the literature
and many more.

\section{A Short History of DNA Computing}

At a certain level of abstraction a single DNA strand is just a sequence
of letters from the alphabet A, C, G, and T.
Two single strands will ``hybridize'' to one another to form
a duplex strand if
each A in one single is paired with a T of the other single and 
each C in one single is paired with a G of the other.
This is called Watson-Crick pairing, in honor of the primary discoverers
of the DNA double-helix.
Watson-Crick pairing provides the foundation for 90\% of DNA computing. 
\index{Watson-Crick pairing}%

DNA nanotechnology started with the pioneering work of Ned Seeman who
was then at the state university of New York at Stony Brook. 
\index{Seeman, Ned}%
As Seeman tells it
\citep{shalaz1}, two colleagues Leonard Lerman
\index{Lerman, Leonard}%
and his post-doc Bruce Robinson 
\index{Robinson, Bruce}%
asked him to look at a DNA structure called
a {\em Holliday Junction} (Figure~\ref{fig:holliday}).
\index{Holliday Junction}%
%
\begin{figure}[p]
	\centering
	\includegraphics[height=40pc]{Holliday.eps}
	\caption{Two configurations of a four-way DNA intersection. 
In one configuration, the top right and the bottom left helices are linked. 
In the other, the top left and the top right are linked. The Watson-Crick attractions are equally long in the two cases, so either state can occur.}
	\label{fig:holliday}
\end{figure}
%
A Holliday junction is a four-stranded structure that resembles a 
four-way road intersection. 
Whereas stable DNA in nature has a linear topology,
Lerman and Robinson were asking Seeman for help in 
building a model to explain how the nonlinear Holliday 
junction appears and disappears.

After helping his colleagues,
Seeman decided that a more interesting question was how to create structures
that would remain non-linear.
Contemplating the Escher painting {\em Depth} which shows
\index{Escher}%
a multi-dimensional school of fish, each having six propeller-like
fins, Seeman noted that not only were the fish topologically six-arm junctions,
but also that the fish were arranged like the molecules in a molecular crystal. There was periodicity front to back, top to bottom, left to right. 

Inspired by this, he constructed a variety of stable non-linear
DNA structures\citep{seeman92}\citep{zhangseeman}, making use of 
Watson-Crick pairing.
\index{Watson-Crick pairing}%
The branch migration structure is a fundamental such stable structure.
\index{branch migration}%
(Figure~\ref{fig:seemanbranch}). Later, he
and his students built a scafolding, 
known as a 
double-crossover (Figure~\ref{fig:seemandouble}),
upon which to attach
other DNA. 
Seeman's success in creating intricate nano-scale sculptures led many
other labs to extend his works
(there are over 50 labs in the world
working on DNA nano-technology as of this writing). 
%
\begin{figure}[p]
	\centering
	\includegraphics[width=.7\textwidth]{seemanbranch.eps}
\caption{Branch Migration:
Some of the ways in which strands of DNA may escape linearity. Watson-Crick pairing (A binds with T, and C binds with G) permits stable
non-linear shapes (Courtesy of Ned Seeman.)}
\label{fig:seemanbranch}
%end{figure}
\vspace*{.15in}
%begin{figure}[hbt]
        \centering
        \includegraphics[width=.7\textwidth]{seemandouble.eps}
\caption{Double-crossover:
This set of interlocking strands is quite strong at
angstrom scales, thus providing a scaffold upon which to attach
other DNA strands.}
\label{fig:seemandouble}
\end{figure}

We, however, will focus
on efforts to make nucleotides do general-purpose computing.
Charles Bennet \citep{Ben1} did the earliest
\index{Bennet, Charles}%
work on models for computing using molecular biological
building blocks.
His idea was to use RNA 
to perform some operations of a Turing machine.
This work was theoretical but suggestive. DNA computing as we know it
requires the ability to make DNA contort in controllable ways,
an achievement that had to wait until Seeman's work and the 
startling paper of Leonard Adleman\citep{Ad1}
\index{Adleman, Leonard}%

Adleman used DNA to solve the directed Hamiltonian Path problem among cities.
\index{Hamiltonian Path problem, defined}%
The Hamiltonian Path problem is to construct a path among simulated cities
such that the path visits every city exactly once.
Adleman showed that this problem could be ``solved'' in DNA by
pouring various single strands into a solution and then fishing out
promising strands using magnetized iron balls 
coated with the complements of the DNA
representing cities.
Because of the algorithm's historical importance 
and the techniques it illustrates,
we describe Adleman's approach in some detail.

To start the process, Adleman represented cities as single strands 
of DNA and legs 
between cities as other single strands. 
Each ``leg strand'' had a 
left half that could bind the DNA for some departure city X 
(via Watson-Crick base pairing) and a right half 
that could bind the DNA for an arrival city Y (figure~\ref{fig:Adlemanexper}).
(As we will see in the physical chemistry section, every
strand has an order. In this descrioption, left half means the first
half of the strand.)
When all city and leg strands were mixed together, the leg strands
held the city strands together in chains of various lengths.



\begin{figure}[p]
        \centering
        \includegraphics{Adlemanexper.eps}
\caption{
Adleman encoded each strand as a sequence of DNA bases (from the alphabet
of A, C, T, G). 
For example, suppose for city B the strand representing ``To B'' ({\em toB}) 
were ATT, 
and the symbol representing ``From B'' ({\em fromB}) were GTCT. 
Strand {\em toB'} would then be the complement of {\em toB} --- TAA. Symbol 
{\em fromB'} would be CAGA. City B would be represented by the concatenation
of {\em toB} and {\em fromB}. An edge from city Y to city B would 
be represented by the ``leg'' strand {\em fromY'} concatenated
with {\em toB'}.
{\em Editors: please note that we want only the top part of this figure.
That is, the part with the airplane and not the part with 
A $\rightarrow$  B $\rightarrow$  C.}
}
\label{fig:Adlemanexper}
\end{figure}


Adleman located double strands whose length indicated that 
they had gone through exactly N cities
(by using a technique called gel electrophoresis that
can measure the length of strands).
\index{gel}%
There was still the possibility that some of those strands included
the same cities several times
while missing other cities. 
So Adleman passed his solution through a series of 
filters that used magnetized iron  balls coated with DNA.
Each ball was complementary 
\index{iron balls}%
to the DNA for 
some city. Any strands that stuck
to all the balls were Hamiltonian paths.
The idea that DNA could ``solve'' even
a small instance of an  NP-complete problem\footnote{The Hamiltonian Path problem, like
other NP-complete problem, has the property that
the only guaranteed solution amounts to trying all possibilities. For the
Hamiltonian Path problem, all possibilities means trying all possible paths.  }
captured the world's imagination.
\index{NP-complete}%


Whereas Adleman had shown how to solve a particular problem,
Paul Rothemund\citep{turing} showed that a Turing machine 
could be 
\index{Rothemund, Paul}%
\index{Turing Machine}%
encoded using DNA and restriction enzymes.
(He had in fact worked out most of these ideas before Adleman's paper
appeared, but he couldn't convince his professors that
his work was interesting. 
This demonstrates that 
even eminent professors
can be as unimaginative as paperweights at times.)
Rotheman's theoretical machine consisted of 
transitions encoded in DNA and restriction enzymes.
When the transitions together with DNA ligase
are applied to a state of the Turing machine
(encoded as DNA),
the machine enters a new state.
Because a Turing Machine can simulate the behavior
of any computer, this achievement showed that arbitrary
computation was in fact possible.

Ogihara and Ray\citep{ogihara}
\index{Ogihara and Ray}%
propose a method for simulating Boolean circuits in DNA.
Benenson et al. \citep{benenson}
\index{Benenson}%
again use restriction nuclease, DNA ligase, and ATP, as well as DNA
that encodes both the ``transition molecules'' and the initial
state of the computation.
In their work,
all inputs are mixed together and the 
chemical computation runs autonomously and asynchronously.

A very recent article by Qian et al.\citep{qian} 
\index{Qian}
has proposed a direct two stack implementation of a Turing machine.
Transitions are designed as bi-directional, reusable ``fuel'' complexes
built entirely from DNA.
For example, a set of fuel complexes that effect the transition
X Y $\rightarrow$ A B
will transform a solution rich in strands X Y to one rich in
strands A B.
The bi-directionality comes from the fact that the fuel complex is not
destroyed by this transition.
Instead, if there is an overwhelming concentration of A B later,
the transition can produce X Y from A B. 
Using such transitions, Qian et al. show how to append onto and remove 
DNA strands from DNA stacks. The authors 
show that this is an efficient simulation of Turing machines.
As in previous approaches, the computation runs autonomously and
asynchronously.
The trouble with asynchronous approaches is that each of these environments
will have millions of Turing Machines. If they are asynchronous, then they
can be in completely different and possibly interfering states.

As we will see in Chapter~\ref{ch04},
Watson-Crick pairing leads to the construction
of DNA walking robots and other nanomechanical devices. Such achievements
are due to a remarkable observation by Bernard Yurke and his 
colleagues\citep{yurke}: Watson-Crick pairing can be ``competitive.''
That is, suppose single strand X is only partially 
paired with single strand Y.
Simplifying slightly (by ignoring
directionality), if X = AAAACCC and Y = AAAAGGG, then X and Y will 
pair at the right (where C hybridizes to G), not at the left.
In their liquid romance, the parts of the strands that hybridize will embrace
one another and the parts that don't will point away from one another.
A tighter embrace leads to a more stable coupling.
Suppose another strand Z (say AATTGGG) comes along 
that has a longer pairing with X (AAAACCC). 
Because this will lead to a tighter embrace,
Z will ``displace'' Y using a zipper-like action as illustrated
in the cartoon of Figure~\ref{fig:tugofwar}.
\index{displacement}%
Think California marriages.

\begin{figure}[hbt]
        \centering
        \includegraphics[width=\textwidth]{RothemundTugofwar.eps}
\caption{In the cartoon, the top right strand displaces
the top left strand because the top right strand has a longer base pairing
with the bottom strand.
}
\label{fig:tugofwar}
\end{figure}


Displacement will allow us to construct instruction
stacks in a DNA solution. 
Each stack is a DNA sculpture containing
heterogeneous strands wrapped together with
fixed strands.
Later, displacement will enable
a simple protocol of pouring in
other fixed strands over specific
time intervals to peel away one strand (an ``instruction'') from
each stack at a time.
This leads to the possibility of parallel synchronous execution.

Martyn Amos \citep{amos} has written a friendly
\index{Amos, Martyn}%
history of computing on biological
substrates. 
He also offers well-founded speculations about
the near and far future. 

The goal of this monograph is much more specialized.
We propose a way to encode arbitrary DNA operations in the natural model of
a clocked parallel machine. 
In operation, this machine would store a program in DNA which would
later ``execute'' thanks to a steady drumbeat of tick and tock single strands.
Just as clocking simplifies the design of electronic computers
and effectively makes programming possible, our simple-to-build proposal
supports branching, loops, and even subroutines.
This will make it possible to ship DNA programs all over
the planet and to run them using two test tubes of clock strands 
and perhaps a few
magnetized iron balls.

\section{Underlying Physical Chemistry}

We lay out some basic features
of the physical chemistry of DNA\citep{intro}.
Understanding these features is not strictly necessary for the reader
seeking to understand only the mathematical structure of DNA
computing, but provides physical intuition.

The DNA polymer (a polymer is just a long
repeating chain of atom clusters) is composed of a flexible backbone
of alternating sugar and phosphate residues.
Each residue consists of a single organic base---adenine,
thymine, cytosine, or guanine---bonded
to a sugar, as shown in Figure~\ref{fig:simplex_2d}.
A chain of nucleotides connected along
a single backbone is referred to as a \textit{single} strand.
\index{nucleotide}%
\index{base}5
%
\begin{figure}[hbt]
	\centering
	\includegraphics[height=.4\textheight]{ch1-fig01.eps}
	\caption[The molecular structure of DNA]{The
molecular structure of a single stranded DNA, coded
\texttt{ATCG} with 5' at the top and 3' at the bottom.
Phosphates are depicted in red, sugars
are depicted in green, and nucleotides are depicted in blue.}
	\label{fig:simplex_2d}
\end{figure}

Because phosphates attach to the sugar ring
at the 5' carbon when viewing the sequence
of sugars in one direction and to the 3' carbon in the other direction,
a strand has an 
\textit{orientation}. 
We follow the convention of describing
single strands from the 5' to 3' direction.
\index{5' to 3'}%
\index{orientation}%
For example,
\texttt{GATTACA} denotes the
bases, listed from the 5' end to the 3' end.
Each phosphate-sugar-base unit is called
a \textit{nucleotide} or \textit{base}.
\index{nucleotide}%
\index{base}%
The binding and unbinding of these backbone
linkages does not occur spontaneously,
but is performed by specific enzymes.
The actions of making or breaking these
sugar-phosphate bonds are termed \textit{ligation}
and \textit{cleavage} respectively.


The nucleotides, however, will spontaneously
stick together thanks to weak hydrogen
bonds, thus \textit{hybridizing} two single
\index{hybridizing}%
strands to form the familiar ``twisted
ladder'' double-helix structure of DNA
as in Figure~\ref{fig:duplex_3d}. A length
of double-stranded DNA is referred to as a \textit{duplex} strand.
\index{duplex}%
%
\begin{figure}[hbt]
	\centering
	\includegraphics[height=.2\textheight]{ch1-fig02.eps}
	\caption[A space-filling model of duplex
DNA]{A 3-dimensional space-filling model
of duplex DNA. The strand on the right
is coded \texttt{ATCG} (oriented 5'--3'
from top to bottom), and the strand on
the left is coded \texttt{CGAT} (also oriented 5'--3' from bottom to top).}
	\label{fig:duplex_3d}
%end{figure}
\vspace*{.15in}
%begin{figure}[hbt]
	\centering
	\includegraphics[height=.3\textheight]{ch1-fig03.eps}
	\caption[An example of Watson-Crick base-pairing]{A
cartoon demonstrating Watson-Crick pairing
of bases by \texttt{A-T} and \texttt{C-G} hydrogen bonds.
	On the right is shown the right-handed
twisting and anti-parallel backbone orientation.}
	\label{fig:duplex_toon}
\end{figure}

This pairing is selective: only pairing
adenine with thymine (the purines A and T) or
cytosine with guanine (the pyrimadines C and G);
Figure~\ref{fig:duplex_toon} illustrates
this as interlocking notches. 
As mentioned above, this
is called the Watson-Crick model of base-pair bonding.
Due to the structure of the DNA polymer,
two single strands will hybridize only if
they are \textit{anti-parallel}---their
\index{anti-parallel}%
orientations are opposite one another---and
will impart a right-handed twist to the
duplex, and shown in Figure~\ref{fig:duplex_toon}.

Because both the base-pairing and the
backbone orientation are fixed for any
given single strand, there is one and
only one \textit{complementary} sequence
\index{complement}%
of nucleotides with which it will hybridize completely;
this complement is obtained by swapping
each base with its partner and reversing
the orientation, thus $\texttt{GATTACA}$
has the complement $\texttt{TGTAATC}$.
By appropriately coding a collection of
single strands, we can thus precisely
control the manner in which they will hybridize.


The above is a slight simplification.
There are, in fact, some exceptions and
pathological cases that complicate the simple Watson-Crick model.
Duplex DNA will change from a clockwise
helix to a counter-clockwise helix called
Z-DNA under the right conditions.
A long sequence of guanine bases will
form a quadruplex helix, in which backbones alternate orientation.
Triple-base bonding, partial bonds, ``incorrect''
pairings such as adenine with guanine,
and more complicated configurations involving
other molecules besides DNA are possible.
For our purposes, we shall assume all
binding follows strict Watson-Crick base
pairing and forms the standard anti-parallel, right-handed duplex
between a single strand and its complement.
We make this assumption because exceptional
cases can typically be avoided without too much difficulty.

The Watson-Crick model allows the construction of linear and branched
DNA structures of quite sophisticated topology.
A \textit{complex} is the general term
\index{complex}%
for such a structure, possibly involving many strands.
For our purposes, such structures together
with various rules and lab protocols for
manipulating them may also be thought of as \textit{machines}.



\section{DNA computation and Engineering}

The relative chemical stability, specificity
of binding, ease of synthesis, and size
of the DNA molecule make DNA an ideal substrate
for molecular computation.
A particular strength of DNA computation
is its inherent parallel nature.
It is easy to replicate strands
hundreds, or even billions of times,
so many thousands of computational instructions
can be carried out simultaneously.

This property suggests that DNA computation
could be used to solve problems and perform
computations that may otherwise scale
poorly with conventional computational
models, particularly certain types of
NP-complete
\index{NP-complete}%
search algorithms, such as the traveling
salesman problem\citep{salesman}.
\index{traveling salesman}%
Unfortunately, the combinatorial explosion of possibilities 
within NP-complete problems
defeats DNA computing
just as it defeats electronic computing.
For example, finding the directed Hamiltonian path for 1,000 cities
would require more nucleotides than there are atoms in the known universe.

Certain approaches
to DNA computation, such as tile-based
constructive computation\citep{winfree96} \citep{universal} \citep{tile} 
have even
been shown to be Turing complete.
\index{Turing Machine}%
While various \textit{direct} implementations
of a Turing machine have been proposed---utilizing
a physical component moving along a modifiable
track\citep{turing}---none have yet been
successfully implemented. 

Parallelism, combined with the specificity
of binding and structural properties,
makes DNA ideal for nanoscale engineering
and self-assembly, even at large scale.
A pioneering example
is Rothemund's recipe for DNA origami, a method that
\index{Rothemund, Paul}%
allowed for the
creation of arbitrary 2-dimensional shapes
out of (i) a single long (7,000+ base)
strand of DNA from a virus and (ii) many short ``staple''
strands\citep{origami}.
Whereas the single long virus strand is rather floppy when left on its own,
a few hundred staple strands can, by Watson-Crick pairing,
cause remote parts of the virus strand to stick together.
Using staples, Rothemund was able to create
a nanometer smiley face.
Now there are software packages available
for rapid prototyping of arbitrary 3D DNA nanostructure shapes
assembled using this technique\citep{origami_3d}.


Other researchers have built
mobile structures
with three specifically
controllable conformations\citep{three_state},
or walkers able to move payloads\citep{walker}.
\index{walker}%
These combined qualities make DNA a rich
medium for nanorobotics, melding both
computation and structural engineering.

In the next chapter, we suggest a language for describing complexes.
Then we will describe transitions among
complexes in terms of that language
and eventually we use the transitions to show how to store
programs inside DNA.
Finally, we discuss the kinds of programming language that will
arise when we can store clocked programs inside DNA.


\clearpage

