Biomedical Engineering Reference
In-Depth Information
4
Formula for the BI Single Tandem Halving Distance
In this section, we show that the BI single tandem halving distance of a totally dupli-
cated genome
G
with
n
distinct markers such that
NG
(
G
)
contains
C
cycles is exactly:
d
t
BI
(
G
)=
n
−
C
2
In other words, we show that enforcing the constraint that successive couples of con-
secutive DCJ operations have to be equivalent to BI operations does not change the
distance even though it obviously restricts the DCJ that can be performed at each step
of the scenario.
In the following,
G
denotes a totally duplicated genome
G
constisting in a single
linear chromosome with
n
distinct markers after the reduction process, and such that
NG
(
G
)
contains
C
cycles. We begin by recalling some useful definitions and properties
of the DCJ operations that allow one to decrease the DCJ halving distance by
1
in the
resulting genome.
Definition 10.
A DCJ operation on
G
producing genome
G
is
sorting
if it decreases
the DCJ halving distance by
1
:
d
p
DCJ
(
G
)=
d
p
DCJ
(
G
)
−
1=
n
−
C
−
1
.
Since the number of distinct markers in
G
is
n
and
d
p
DCJ
(
G
)=
n
1
,then
NG
(
G
)
contains
C
+1
cycles. In other words, a DCJ operation is sorting if it increases
the number of cycles in
NG
(
G
)
by
1
.
Given
(
uv
)
an adjacency of
G
that is not a double-adjacency, we denote by DCJ
(
uv
)
the DCJ operation that cuts adjacencies
(
ux
)
and
(
y v
)
to form adjacencies
(
u v
)
and
(
yx
)
,making
(
uv
)
a double-adjacency.
−
C
−
Property 3.
Let
(
uv
)
be an adjacency of
G
that is not a double-adjacency, DCJ
(
uv
)
is a sorting DCJ operation.
Proof.
DCJ
(
uv
)
increases the number of cycles in
NG
(
G
)
by
1
,bycreatinganew
cycle composed of adjacencies
(
uv
)
and
(
u v
)
.
Definition 11.
Let
(
uv
)
,
(
ux
)
, and
(
y v
)
be adjacencies of
G
.The
interval
of the
adjacency
(
uv
)
, denoted by
I
(
uv
)
is either:
-
the interval
[
x
;
y
]
if
(
ux
)
<
(
y v
)
. In this case, we denote it by
]
u
;
v
[
,or
-
the interval
[
v
;
u
]
if
(
y v
)
<
(
ux
)
.
For example, the intervals of the adjacencies in genome
(
)
are depicted
in figure 2. Note that, given an adjacency
(
uv
)
of
G
,if
(
uv
)
is a double-adjacency
then the interval
I
(
uv
)
is empty, otherwise DCJ
(
uv
)
is the excision operation that
extracts the interval
I
(
uv
)
to make it circular, thus producing the adjacency
(
u v
)
.
Two in ter vals
I
(
ab
)
and
I
(
xy
)
are said to be
overlapping
if their intersection is
non-empty, and none of the intervals is included in the other. It is easy to see, following
Property 1, that given two adjacencies
(
ab
)
and
(
xy
)
of
G
such that
I
(
ab
)
and
I
(
xy
)
are non-empty intervals, the successive application of DCJ
(
ab
)
and DCJ
(
xy
)
◦
21231 3
◦
Search WWH ::
Custom Search