
\def\CRTITLE{Storing Clocked Programs Inside DNA: A Simplifying Framework for Nanocomputing}
\def\HALFTITLE{Storing Clocked Programs\\[8pt]Inside DNA\\[8pt]{\Large A Simplifying Framework for Nanocomputing}}
\def\TITLE{Storing Clocked Programs\\[4pt]Inside DNA\\[4pt]{\Large A Simplifying Framework for Nanocomputing}}
\def\AUTHORA{Jessica P. Chang}
\def\AFFILIATION{Courant Institute, New York University}
\def\AUTHORB{Dennis E. Shasha}
\def\AUTHORS{\AUTHORA\ and \AUTHORB}
\def\LECTURE{\ \#3}
\def\lcSYNTHESIS{Synthesis Lectures on Computer Science}
\def\SYNTHESIS{\uppercase{Synthesis Lectures on Computer Science}}
%def\EDITOR{Thornton, \textit{University}}


%%%%%%%%%%%% HALF TITLE PAGE 1-2

\thispagestyle{emptyrule}

\halftitle{\HALFTITLE}

\clearpage


%%%%%%%%%%%%% SERIES PAGE 3

\blankpage

{

\raggedright					% do not split words in the Synthesis Series

\thispagestyle{emptyrule}
\chapter*{\lcSYNTHESIS}
\thispagestyle{emptyrule}

%vspace*{.75pc}
%seriesTitle{Editor}
%seriesAuthor{\textbf{\EDITOR}}

%vspace*{.55pc}
%noindent
%...SYNTH COPY

\vspace*{.75pc}
\seriesTitle{\CRTITLE}
\seriesAuthor{\AUTHORS}
\noindent2011

\vspace{.75pc}  % 3
\seriesTitle{Science Fiction Prototyping}
\seriesAuthor{Brian D. Johnson}
\noindent 2011

\vspace{.75pc}  % 2
\seriesTitle{Analytical Performance Modeling for Computer Systems}
\seriesAuthor{Y.C. Tay}
\noindent 2010

\vspace{.75pc}  % 1
\seriesTitle{The Theory of Timed I/O Automata}
\seriesAuthor{Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager}
\noindent 2006

}

\clearpage


%%%%%%%%%%% COPYRIGHT PAGE 4

\thispagestyle{emptyrule}
\vbox{
\parindent0pt\leftskip0pt\rightskip0pt%
\vspace*{66pt}
{\fontsize{9}{12}\selectfont%
Copyright \copyright\ \ \ 2011 by Morgan \& Claypool\\\\[7pt]
	All rights reserved. No part of this publication may be reproduced,
	stored in a retrieval system, or transmitted in any form or by any
	means---electronic, mechanical, photocopy, recording, or any other
	except for brief quotations in printed reviews, without the prior
	permission of the publisher.\\[19pt]
\hspace*{18pt}\CRTITLE\\[3.5pt]	
\hspace*{18pt}\AUTHORS\\[3.5pt] 
\hspace*{18pt}\url{www.morganclaypool.com}\\[19pt]
\hspace*{18pt}ISBN: 9781608456956\qquad\hspace*{4.5pt}paperback\\
\hspace*{18pt}ISBN: 9781608456963\qquad\hspace*{4.5pt}ebook\\[21pt]
%hspace*{18pt}ISBN: 9781598296167\qquad\hspace*{4.5pt}hardback\\[21pt]
\hspace*{18pt}DOI  10.2200/S00343ED1V01Y201103CSL004\\[21pt]	
%
\hspace*{18pt}A Publication in the Morgan \& Claypool Publishers series\\
\hspace*{18pt}{{\it\uppercase{\SYNTHESIS}}}\\[10.5pt]
\hspace*{18pt}{Lecture\LECTURE}\\
%hspace*{18pt}Series Editor: \EDITOR\\
%hspace*{18pt}First Edition\\[3.5pt]
%hspace*{18pt}10 9 8 7 6 5 4 3 2 1\\\\
\hspace*{18pt}Series ISSN\\
\hspace*{18pt}\lcSYNTHESIS\\
%hspace*{18pt}{ISSN pending.}
\hspace*{18pt}{Print 1932-1228\quad Electronic 1932-1686}
}
}

\clearpage


%%%%%%%%%%%% FULL TITLE 5

\thispagestyle{emptyrule}
\title{\TITLE}

\vspace*{2pc}
\authorname{\AUTHORS}
\authoraffiliation{\AFFILIATION}

\vfill
\synthesis{\SYNTHESIS\LECTURE}
\morganlogo

\clearpage


%%%%%%%%%%%% ABSTRACT AND KEY TERMS ( \keywords{ ... } ) 6

\thispagestyle{emptyrule}

\ABSTRACT
\noindent
In the history of modern computation,
large mechanical calculators preceded computers.
A person would sit there punching keys
according to a procedure and a number would eventually appear.
Once calculators became fast enough, it
became obvious that the critical path 
was the punching rather than the calculation itself.
That is what made the stored program concept vital to further progress.
Once the instructions were stored in the
machine, the entire computation could run at the speed of the machine.

This book shows how to do  the same thing for DNA computing.
Rather than asking a robot or a person
to pour in specific strands at different
times in order to cause a DNA computation
to occur (by analogy to a person punching
numbers and operations into a mechanical
calculator), the DNA instructions are
stored within the solution and guide the entire computation.
We show how to store straight line programs,
conditionals, loops, and a rudimentary form of subroutines.

To achieve this goal, the book proposes
a complete language for describing the
intrinsic topology of DNA complexes and
nanomachines, along with the dynamics of such a system.
We then describe dynamic behavior using
a set of basic transitions, which operate
on a small neighborhood within a complex in a well-defined way.
These transitions can be formalized as
purely syntactical functions of the string representations.

Building on that foundation, the book
proposes a novel machine motif which constitutes
an instruction stack, allowing for the
clocked release of an arbitrary sequence
of DNA instruction or data strands.
The clock mechanism is built of special
strands of DNA called ``tick'' and ``tock.''
Each time a ``tick'' and ``tock'' enter a DNA solution, a strand
is released from an instruction stack (by analogy to
the way in which  as a clock cycle in an electronic computer causes
a new instruction to enter a processing unit).
As long as there remain strands on the
stack, the next cycle will release 
a new instruction strand.
Regardless of the actual strand or component
to be released at any particular clock
step, the ``tick'' and ``tock'' fuel strands
remain the same, thus shifting the burden
of work away from the end user of a machine and easing operation.
Pre-loaded stacks enable the concept of
a stored program to be realized as a physical DNA mechanism.

A conceptual example is given of such a stack operating 
a walker device.
The stack allows for a user to operate
such a clocked walker by means of simple
repetition of adding two fuel types, in
contrast to the previous mechanism of
adding a unique fuel---at least 12 different
types of strands---for each step of the mechanism.

We demonstrate by a series of experiments conducted in Ned Seeman's lab
that it is possible to ``initialize'' a clocked stored program
DNA machine.
We end the book with a discussion of the design features of a programming
language for clocked DNA programming.
There is a lot left to do.
%end ABSTRACT

\keywords{%
DNA computing, parallel programming, clocks, stored program concept,
programming language design
}

\vfill

\clearpage


%%%%%%%%%%%%% DEDICATION  7-8


%{
%\clearpage
%\thispagestyle{emptyrule}
%
%\vspace*{13pc}\LARGE\it
%\centerline{To my father, Shengyong Li,}
%}
%
%\clearpage
 

%%%%%%%%%%%%%%%%%%%%%%%% TOC %%%%%%%%%%%%%%%%%%

%\blankpage

{
\pagestyle{plain}
\tableofcontents
}

\clearpage
 
 
%%%%%%%%%%%%%%%%%%%%%%%% PREFACE %%%%%%%%%%%%%%%%%%%
 
 
%\blankpage
%
%{
%\chapter*{Preface}
%\addcontentsline{toc}{chapter}{\numberline{}{Preface}}
%\thispagestyle{emptyrule}
%\markboth{PREFACE}{PREFACE}
%
%
%\vspace*{2pc}
%\noindent
%\AUTHORS\newline
%February 2011
%}
%
%\clearpage


%%%%%%%%%%%%%%%%%%%%%%%% ACK %%%%%%%%%%%%%%%%%%%


%blankpage

\chapter*{Acknowledgments}
\addcontentsline{toc}{chapter}{\numberline{}{Acknowledgments}}
\thispagestyle{emptyrule}
\markboth{ACKNOWLEDGMENTS}{ACKNOWLEDGMENTS}


We would like to thank Michelle Lynn Hall
for assistance rendering chemical diagrams and proofreading.
We would also like to thank Ada Zhang
for her knowledge of laboratory procedures
and insights therein. These helped
with our preliminary modeling of reaction speed.
A substantial thanks goes to Christofer
Hedbrandh for his programming expertise
in implementing a software engine that
computes stable states.
We did all our experiments in Professor Ned Seeman's lab.
Ned also provided many invaluable reality checks.

Readers of the manuscript included Pearl Chin, Dalibor
Frtunick, Panta da Silva, and Sarah Smith, 
all of whom provided excellent comments.
Copyeditor ...

Thanks to our editor Brendan Curry and to W. W. Norton for allowing
us to reuse some of the illustrations from the book {\em Natural Computing}.

This work has been partially supported by the U.S. National Science
Foundation under grants
IIS-0414763,
DBI-0445666,
DBI-0421604,
N2010 IOB-0519985,
N2010 DBI-0519984,
DBI-0421604,
and
MCB-0209754.
This support is greatly appreciated.


\vspace*{2pc}
\noindent\AUTHORS\\
\noindent March 2011
 
\clearpage

\blankpage

