Biology Reference
In-Depth Information
or by the state of the surrounding DNA. Fourth, the length of DNA between a
pair of inversion sites is such that the invertases can flip it. Fifth and finally, for
simplicity, our input alphabet, which is the set of different invertases, is assumed
to be presented as a sequence of single activities, each element of which is well
separated in time and on long enough time-scale to effect a flip. No invertases are
present more than once in a sequence. Thus, for N invertases there are N! possible
ordered input sequences to our device.
Our device is defined by an arrangement of the N pairs of inversion sites on
DNA with no pair appearing more than once in the device. While there might be
multiple devices encoded on a single duplex of DNA, we call a single (fully con-
nected) device a set of pairs of sites for which every pair brackets a region of DNA
that overlaps another region bracketed by at least one other pair of the device. Fig-
ure 1 shows possible arrangements of sites for devices accepting one (Figure 1A),
two (Figure 1B&C) and three recombinase (Figure 1D) inputs. The number of
such possible configurations increases rapidly with number of invertases. Assuming
that configurations that are identical under shuffling of site identity are equivalent
(that is, x-y-x-y is equivalent to y-x-y-x), an enumeration of all possible devices with
n inputs a(n) suggests that with n = N-1,
n
−
1
= > =−− −
∑
.
(The inference of formulae from sequence was provided by the Online Encyclo-
pedia of Integer Sequences.) By the time one has ten invertases there are more
than 1010 possible arrangements of sites. The graph of possible configurations as
a function of number of invertases, Figure 1E, shows the better than exponential
increase in number of configurations as a function of N. If we assume we need
at least 500 basepairs between sites for flipping to occur and each site is about 30
bp, a device with N inputs has a minimal size of around 30*2*N+500 basepairs
(overlapping regions can decrease this slightly). For a device with 10 inputs then,
apart from the DNA encoding the expression of the recombinases, 1.1 kilobases
is all that is required to encode any of ten billion machines. This is the length of
an average sized gene.
Each of these devices behaves differently under the N! possible inputs. Figure
1A-C shows the state transition graphs for all configurations of 1 and 2 invertase
input devices. Each transition shows the transformation of one DNA state to an-
other for each allowed sequence of inputs (see caption). Theoretically, for certain
configurations, starting from an initial state of the device (state 0), it is possible
that every possible history of input is recordable in the state of the DNA. That is, it
is possible to determine which even partial sequence of inputs the device has seen
by sequencing the DNA between its outermost sites. Simply counting the internal
nodes of the state transition graphs like those in Figure 1C shows that the number
of states (excluding state 0) for such devices is the number of permutations of
non-empty subsets of {1,…,N} or
a
(0)
1;
forn
0,
an
(
)
(2
n
1) !!
(2
k
1) !!
an k
(
)
k
=
1
N
. A graph of this function
=
å
SN
( )
kCN k
!( ,)
=
k
1
Search WWH ::
Custom Search