![[Previous]](http://www-psrg.lcs.mit.edu/Hyperlatex-1.3/docsleft.gif)
![[Up]](http://www-psrg.lcs.mit.edu/Hyperlatex-1.3/docsupar.gif)
![[Next]](http://www-psrg.lcs.mit.edu/Hyperlatex-1.3/docsrigh.gif)
Armed with this tool, our approach to designing DNA machines proceeds
as follows. Let us imagine that our initial single-stranded sequence
of DNA encodes a string of logical symbols from some alphabet. Each
symbol is encoded by a certain base-sequence, and the base-sequences
of subsequent symbols in a string are simply concatenated together to
form the encoding for the whole string. For example, if logical
0 is encoded as 5'(AGATCACGTT)3', and logical 1 is
5'(GCGGCGATGA)3', then the string 10100 is given by the base
sequence
5'- GCGGCGATGAAGATCACGTTGCGGCGATGAAGATCACGTTAGATCACGTT ->3'.
[ 1 ][ 0 ][ 1 ][ 0 ][ 0 ]
Given this interpretation of DNA base sequences as symbol-strings, and
given our knowledge of oligo-directed mutagenesis, a natural sort of
operation we might want to perform is to transform all occurences of a
certain source substring of logical symbols within a long
string into a certain other result substring, which may or may
not be the same length. For example, we might transform all 10
sustrings to 011, changing the string in the above example to
0110110. In computer science terminology, this is what is
known as an application of a string-rewriting rule. By
repeatedly applying a set of such rules, complex
information-processing can be performed. In fact, such
string-rewriting systems are well known to be universal models
of computation [Book-Otto-93]. Thus, if we can implement
string-rewriting rules with mutagenesis, we will be in good shape for
building complex DNA machines.
The basic idea for how to implement a rewrite rule is simple: we can imagine including in the reaction mixture an oligo that is almost complementary to the source substring, so that it will bind specifically to it. The oligo will introduce mutations that yield the desired result string (or rather, its complement). It turns out that this simple approach suffices for implementing a restricted class of string-rewriting systems that is sufficient for counting DNA replications. To implement more complex string-rewriting systems requires some modifications to the basic idea, such as varying the length of symbol encodings, or performing the rewrite gradually in several steps. These modified versions of the idea have been verified in simulation. However, implementing a rewriting system complex enough to perform arbitrary computations raises a few additional problems, for which we have found solutions in principle that remain to be worked out in detail.