Biomedical Engineering Reference
In-Depth Information
d
p
DCJ
(
G
)
Next, we show that if
n
=2
or
n
=3
,then
d
t
BI
(
G
)=1
and
2
≤
≤
3
.
)
, in which case a BI
can swap
a
and
b
to produce a single tandem duplicated genome, or as
(
If
n
=2
, then the genome can be written, either as
(
◦
abb a
◦
)
,in
which case a BI can swap
a
and
ab
to produce a single tandem duplicated genome.
If
n
=3
, then the genome has two double-adjacencies to be constructed, of the form
(
a b
)
,
(
x y
)
, with
(
ab
)
and
(
xy
)
being two adjacencies already present in the genome
such that
b
=
x
or
b
=
x
and
a
and
y
are distinct markers. One can rewrite
(
ab
)
and
(
xy
)
as single markers since they will not be splitted, which makes a genome with
4 markers such that at most 2 are misplaced. Then, a single BI can produce a single
tandem duplicated genome.
Now, it is easy to see to see that if
n
=2
or
n
=3
,then
d
p
DCJ
(
G
)=
n
◦
a abb
◦
−
C
≤
3
.
Finally, if
n
=2
or
n
=3
,then
d
p
DCJ
(
G
)
2
, otherwise we would have
d
p
DCJ
(
G
)=1
which would imply, as
G
consists in a single linear chromosome,
d
t
BI
(
G
)=0
.In
conclusion, if
n>
3
then there exist two compatible intervals in
≥
I
(
G
)
, otherwise if
d
p
DCJ
d
p
DCJ
(
G
)
n
=2
or
n
=3
,then
d
t
BI
(
G
)=1
and
2
≤
≤
3
. Therefore
d
t
BI
=
2
=
n−C
2
.
5
Sorting Algorithm
In Section 4, we showed that if a genome
G
contains more than three distinct markers
after reduction then there exist two compatible intervals in
(
G
)
inducing a BI to per-
form. If
G
contains two or three distinct markers then the BI to perform can be trivially
computed. Thus the main concern of this section is to describe an efficient algorithm
for finding compatible intervals when
n>
3
.
As in Section 4, in the following,
G
denotes a genome consisting of
n
distinct mark-
ers after reduction. It is easy to show that the set of intervals
I
I
(
G
)
can be built in
O
(
n
)
time and space complexity.
We now show that finding 2 compatible intervals in
I
(
G
)
can be done in
O
(
n
)
time
and space complexity.
Property 6.
If
n>
3
, then all the smallest intervals in
I
(
G
)
that are not of type 2
admit compatible intervals.
Proof.
Let
J
be a smallest interval that is not of type 2 in
I
(
G
)
.As
J
is not of type 2,
then
J
has compatible intervals if
J
is not of type 1.
Let us suppose that
J
is of type 1, then for any adjacency
(
ab
)
such that markers
a
and
b
are not in
J
,
a
and
b
are in
J
,andthen
I
(
ab
)
is strictly included in
J
and
I
(
ab
)
can't be of type 2. Such adjacency does exist as there are
n>
3
markers not included
in
J
. Therefore
J
cannot be a smallest interval that is not of type 2.
We are now ready to give the algorithm for sorting a duplicated genome
G
into a single
tandem duplicated genome with
n−C
2
BI operations.
Theorem 3.
Algorithm 1 reconstructs a single tandem duplicated genome with a BI
scenario of length
n−C
in
O
(
n
2
)
time and space complexity, by computing pairs of
2
sorting DCJ operations.
Search WWH ::
Custom Search