Information Technology Reference
In-Depth Information
Ta b l e 2 . 6
A DNA extraction algorithm providing the strings of length
n
including
γ
as sub-
string, in a given a pool
P
XPCR
−
Extract
(
P
,
n
,
γ
)
1.
P
:
=
in f ix
(
P
,
α
,
β
)
;
2.
P
0
:
=
separate
(
P
,
n
)
;
3.
(
P
1
,
P
2
)
:
=
split
(
P
0
)
;
¯
4.
P
1
:
=
PCR
(
P
1
,
α
,
γ
)
;
¯
5.
P
2
:
=
PCR
(
P
2
,
γ
,
β
)
;
6.
P
1
:
=
P
1
−
separate
(
P
1
,
n
)
;
7.
P
2
:
=
P
2
−
separate
(
P
2
,
n
)
;
=
mix
(
P
1
,
P
2
)
8.
Q
:
;
¯
=
PCR
(
Q
,
α
,
β
)
9.
Q
:
;
10.
Q
:
=
separate
(
Q
,
n
)
;
11.
output
Q
.
In the joining process, pieces which do not have length
n
are removed. For this rea-
son, the process must be iterated for each length of strings of the initial pool. The
algorithm reported in Table 2.6 provides all the strings where
γ
occurs, previously
elongated by the prefix
. This algorithm was tested in vitro
where, in a very heterogeneous DNA pool, all the types of strands including sub-
strands of a given type, and only they, were extracted. Therefore,
XPCR
extraction
proved to be correct and complete [28].
A useful warning about the
XPCR
-Extract algorithm is given by the follow-
ing observation. If in a family of initial genes there are two different genes, say
<
ϕγψ
>
α
andbythesuffix
β
oc-
curs in exactly the same position, then the method will give, as extracted genes, also
their chimeric combinations
and
<
σγρ
>
, that have the same length and where the substring
γ
<
σγψ
>
and
<
ϕγρ
>
. In other words, if we define
Recombine
(
L
,
γ
)=
{<
αγβ
> | <
αγδ
>,<
ηγβ
> ∈
L
}
,then
Extract
(
P
,
γ
)
co-
incides with
Recombine
(
Type
(
P
)
,
γ
)
. In this case, further checks are necessary for
realizing a reliable extraction.
2.5.3
DNA Recombination by
XPCR
Let
P
a DNA pool of type
.The
problem of generating all possible recombinations of pools
P
and
Q
is that of obtain-
ing a pool of type
L
{
α
1
,
α
2
,...,
α
n
}
and
Q
a pool of type
{
β
1
,
β
2
,...,
β
n
}
.
Of course
L
contains 2
n
different strings; we call it the
n
dimensional complete re-
combination of
P
and
Q
. In DNA Computing this is an important step for encoding
all the possible solutions of a combinatorial problem. For example, if
=
{
η
1
η
2
...
η
n
|
η
1
∈{
α
1
,
β
1
},
η
2
∈{
α
2
,
β
2
}...
η
n
∈{
α
n
,
β
n
}}
α
,
β
i
encode
i
