Biomedical Engineering Reference
In-Depth Information
I
(2 3) =]2 ;
3
[
I
(2 1) =]2; 1[
I
(1 3) =]1 ; 3[
(
◦
◦
)
2
1
2
3
1
3
I
(1 2) = [2 ; 1]
I
(3 1) = [1 ; 3]
Fig. 2.
I
(
G
)=
]2; 1[
,
[
2
;
1
]
,
]2 ; 3[
,
[
1
;
3
]
,
]1 ; 3[
, the set of intervals of
G
=
(
◦
21231 3
◦
)
depicted as boxes. The two boxes with thick lines represent two overlapping
intervals of
I
(
G
)
inducing a BI which exchanges
2
and
3
is equivalent to a BI operation if and only if
I
(
ab
)
and
I
(
xy
)
are overlapping. Note
that in this case neither
(
ab
)
, nor
(
xy
)
can be double-adjacencies in
G
since their
intervals are non-empty. Figure 2 shows an example of two overlapping intervals.
The following property states precisely in which case the successive application of
DCJ
(
ab
)
and DCJ
(
xy
)
decreases the DCJ halving distance by
2
, meaning that both
DCJ operations are sorting.
Property 4.
Given two adjacencies
(
ab
)
and
(
xy
)
of
G
, such that
I
(
ab
)
and
I
(
xy
)
are overlapping, the successive application of DCJ
(
ab
)
and DCJ
(
xy
)
decreases the
DCJ halving distance by
2
if and only if
x
=
a
and
y
=
b
.
Proof.
If
x
=
b
, then the successive application of DCJ
(
ab
)
and DCJ
(
xy
)
increases the number of cycles in
NG
(
G
)
by
2
, by creating two new 2-cycles. Otherwise,
DCJ
(
ab
)
first creates a new cycle that is then destroyed by DCJ
(
xy
)
.
=
a
and
y
We denote by
I
(
G
)
, the set of intervals of all the adjacencies of
G
that do not contain
marker
◦
.
Remark 1.
Note that, if
G
contains
n
distinct markers, then there are
2
n
−
1
adjacencies
in
G
that do not contain marker
◦
, defining
2
n
−
1
intervals in
I
(
G
)
.
Definition 12.
Two intervals
I
(
ab
)
and
I
(
xy
)
of
I
(
G
)
are said to be
compatible
if
they are overlapping and
x
=
a
and
y
=
b
.
In the following, we prove the BI single tandem halving distance formula by showing
that if genome
G
contains more than three distinct markers,
n>
3
, then there exist
two compatible intervals in
(
G
)
,andif
n
=2
or
n
=3
then
d
t
BI
(
G
)=1
and
I
d
p
DCJ
(
G
)
2
3
. This means that there exists a BI halving scenario
S
such that all
BI operations in
S
, possibly excluding the last one, are equivalent to two successive
sorting DCJ operations.
From now on, until the end of the section,
(
ab
)
is an adjacency of
G
that is not a
double-adjacency,
A
is a genome consisting in a linear chromosome
≤
≤
L
and a circular
chromosome
, obtained by applying the
sorting DCJ
, DCJ
(
ab
)
,on
G
.
If there exists an interval
I
(
xy
)
in
C
(
G
)
compatible with
I
(
ab
)
, then applying
DCJ
(
xy
)
on
A
consists in the integration of the circular chromosome
I
C
into the linear
chromosome
such that the adjacency
(
x y
)
is formed. Such an
integration
can only
be performed by cutting an adjacency
(
xu
)
in
L
C
and an adjacency
(
v y
)
in
L
(or
Search WWH ::
Custom Search