Information Technology Reference
In-Depth Information
the two possible values of a Boolean variable
x
i
, then any string of
L
usually encodes
a possible solution of the problem. True solutions are obtained by generating
L
and
then by extracting strings which satisfy the requirements of the problem. But, apart
from this DNA computing interest, DNA recombination has an important biological
meaning. For example, in the immunological system recombination is a key feature
for generating the antibody repertory which is essential to the security system pre-
serving the biological identity. However, in general, DNA pools generated by
XPCR
recombination could be very useful in the analysis of many aspects related to DNA
hyper-variability.
Let us present a DNA recombination method based on
XPCR
. We show that a
simple and efficient algorithm based on
XPCR
can provide the
n
dimensional com-
plete recombination of
P
and
Q
. Let us consider the following four
initial sequences
,
where
n
is an odd number (if
n
is even, the roles of
α
n
and
β
n
are inverted in the last
two sequences):
Positive
:
η
=
<
α
α
α
α
...
α
>
n
1
1
2
3
4
Negative
:
η
=
<
β
β
β
β
...
β
>
n
2
1
2
3
4
Positive-Negative
:
η
=
<
α
β
α
β
...
α
>
3
1
2
3
4
n
Negative-Positive
:
η
=
<
β
α
β
α
...
β
>.
4
1
2
3
4
n
Let us call
α
-string any element of
{
α
1
,
α
2
,...,
α
n
}
and
β
-string any element of
{
β
1
,
β
2
,...,
β
n
}
. The language
L
is the set of all the possible ordered combinations of
r
γ
−→
ζ
n
α
-strings and
β
-strings. We call
XPCR
rule
r
γ
, and write it as
ξ
1
,
ξ
2
,there-
lation between strings
ξ
1
,
ξ
2
,
ζ
that holds when
ξ
1
=
<
αδγ
...>
,
ξ
2
=
<...
γθβ
>
,
and
ζ
=
<
αδγθβ
>
. Any string that is a combination of
α
-strings and
β
-strings
can be obtained from
η
1
,
η
2
,
η
3
,
η
4
by suitable
XPCR
rules
r
γ
where
γ
is an
α
-
string or a
β
-string. For example, with
n
=
7, the string
α
1
α
2
β
3
α
4
β
5
β
6
β
7
, can be
obtained in the following way:
r
r
β
5
−→
α
1
α
2
β
3
α
4
β
5
β
6
β
7
.
α
2
−→
α
1
α
2
β
3
α
4
β
5
α
6
β
7
,
η
2
η
1
,
η
4
It can be easily shown that the order of application of the rules is not relevant,
because the same string can be also obtained by permuting the order of application
of the rules (from the same initial strings).
Let us consider the set of
XPCR
rules
R
=
{
r
α
2
,
r
α
3
,...
r
α
n
−
1
,
r
β
2
,
r
β
3
,...
r
β
n
−
1
}
.
A “quaternary
XPCR
recombination” which produces
L
from
is ef-
fectively specified by the algorithm displayed in Table 2.7. A completeness claim of
our quaternary
XPCR
recombination method is given by the following proposition,
which is an easy consequence of
XPCR
definition and of the particular structure of
the pool to which we apply this recombination method [30].
{
η
1
,
η
2
,
η
3
,
η
4
}
Proposition 2.3 (Recombination Method).
If all the X PCR rules of R are applied
to a DNA pool of Type
, then a final DNA pool is obtained of Type
{
ξ
1
ξ
2
...
ξ
n
|
ξ
1
∈{
α
1
,
β
1
},
ξ
2
∈{
α
2
,
β
2
}...
ξ
n
∈{
α
n
,
β
n
}}
{
η
1
,
η
2
,
η
3
,
η
4
}
.
