![[Up]](http://www-psrg.lcs.mit.edu/Hyperlatex-1.3/docsupar.gif)
![[Next]](http://www-psrg.lcs.mit.edu/Hyperlatex-1.3/docsrigh.gif)
Our first example is a simple machine designed so that each new strand
that is produced encodes the number of generations of copying that
were required to produce it. Let our alphabet consist of 3 symbols,
0, 1, and 2, and let the initial strand encode
the string:
1 0 0 0 0 0 0 ...
and suppose that on subsequent replication steps we wish to produce
strands encoding the following series of strings:
Initial strand: 1 0 0 0 0 0 0 ...
Step 1: 1 2 0 0 0 0 0 ...
Step 2: 1 2 1 0 0 0 0 ...
Step 3: 1 2 1 2 0 0 0 ...
Step 4: 1 2 1 2 1 0 0 ...
Step 5: 1 2 1 2 1 2 0 ...
etc.
In other words, we wish to move down the strand from the initial
1, painting a pattern with alternating 1's and
2's. This behavior can be produced by the following pair of
rewrite rules (written here with source strings on top, result strings
on bottom):
1 0 2 0
--- ---
1 2 2 1
To encode these rules in oligonucleotides, a straightforward approach
is to choose the encoding of both 1 and 2 to be similar
to the encoding of 0, so that an oligo encoding 1 2 can
directly bind to the part of the template that encodes 1 0, and
an oligo encoding 2 1 can bind to the part encoding 2 0.
(We can set things up so that these oligos cannot bind anywhere else,
due to an overly-large number of mismatches.)
Each oligo, of course should actually be complementary in orientation and base composition to the template to which it is supposed to bind, so, for example, if the initial template is encoded in complementary form, i.e.,
!1 !0 !0 !0 !0 !0 !0
<--------------------
(where the arrow indicates the 5' to 3' direction, and the !1
indicates the reverse complement of the "normal" encoding of
1), then we would want to have one oligo that binds to this
template as follows:
----->
1 2
: :
!1 !0 !0 !0 !0 !0 !0
<--------------------
and, if we want to introduce another change on the very next step, we
would also need an oligo that binds to the resulting new strand as
follows:
-------------------->
1 2 0 0 0 0 0
: :
!2 !1
<-----
(For expository purposes we are ignoring the priming sites and primers
that must of course be present at each end.) Unfortunately, this
mixture of oligos would yield an unwanted side product, namely chains
of these two oligos, bound to each other, e.g.,
----->----->
1 2 1 2
: : :
!2 !1 !2 !1
<-----<-----
Fortunately, there is an alternative implementation that avoids this
problem, at the cost of only producing a change on alternate cycles,
and that is to have both oligos be of the same "sign," so to speak:
-----> ----->
2 1 1 2
so that they will not bind to each other. The oligos will thus only
bind to "negative" templates, and positive templates will be copied
with no alteration. However, the number of 1's and 2's along a strand
can still be considered to be roughly proportional to the number of
generations of copying that separate it from the original. This
proportion is only rough, because there is a competition between the
1 2 and 2 1 strands for binding sites (see this figure).
----->
1 2
: :
. .
-----> .
2 1 .
: : .
. . .
!2 !1 !0 !0
<------------
Figure 2 : Both oligos want to bind to the
!1. They cannot both bind.
2 1 oligo will always be the one bound,
because it will bind first during the few seconds it takes to lower
the temperature to the point at which the mismatched one could bind.
This leads to an upper bound on oligo concentrations of (we estimate)
around 0.1uM (microMolar). This upper limit on
oligo concentration, in turn, places a lower bound on oligo lengths,
and an upper bound on the number of mismatches that can be tolerated
in oligos of a given length and still have binding occur.
Fortunately, we have found that these limits are reasonable.
The exact design of the oligos for machine, and the results of its
simulation are presented in a later section. For now, a final note on
this machine is that although it yields the desired behavior on the
given input stand, it does not implement solely the two rewrite rules
given above. It also simultaneously implements the two rules
(0 1) -> (2 1) and (0 2) -> (1 2). In other words, if
there were zeroes on the other side of the initial 1, they
would be written over as well. This is due to the fact that our
oligos do not really define a unique source string to which they will
stick; rather they will stick to any site where one of the symbols
matches and the other, if not a match, is a zero. Each oligo
therefore defines a set of rewrite rules, rather than a single rule.
This is a property shared by all the oligo systems we have
investigated; fortunately, it does not appear to ultimately detract
from the method's computational power, as we will discuss in a later
section.