Biomedical Engineering Reference
In-Depth Information
inversely) to produce adjacencies
(
x y
)
and
(
vu
)
. This means that there must be an
adjacency
(
xy
)
in either
C
L
such that
x
is in
C
and
y
in
L
or
or inversely. Hence, we
have the following property :
Property 5.
C
cannot
be reintegrated into
L
by applying a sorting DCJ, DCJ
(
xy
)
,on
A
if and only if either:
(1) for any adjacency
(
xy
)
in
C
(resp.
L
), markers
x
and
y
are in
L
(resp.
C
), or
(2) for any adjacency
(
xy
)
in
C
(resp.
L
), markers
x
and
y
are also in
C
(resp.
L
).
Proof.
If there exists no adjacency
(
xy
)
in
A
such that
x
is in
C
and
y
in
L
or inversely,
then
A
necessarily satisfies either
(1)
,or
(2)
.
Definition 13.
An interval
I
(
ab
)
in
(
G
)
is called
interval of type 1
(resp.
interval of
type 2
)if
DCJ
(
ab
)
produces a genome
A
satisfying configuration
(1)
(resp. configu-
ration
(2)
) described in Property 5.
I
For example, in genome
(
◦
21132 3
◦
)
,
I
(13)
is of type 1 as DCJ
(13)
produces
genome
(
◦
213
◦
)(132)
;
I
(2 3)
is of type 2 as DCJ
(2 3)
produces genome
(
)(1 1)
.
Now we give the maximum numbers of intervals of type 1 and type 2 that can be
contained in genome
G
.
◦
232 3
◦
I
(
G
)
is 2.
Lemma 2.
The maximum number of intervals of type 1 in
Proof.
First, note that there cannot be two intervals
I
and
J
of
=
J
,
and both
I
and
J
are of type 1. Now, if
I
is an interval of type 1, there can be at
most two different adjacencies
(
xy
)
and
(
uv
)
such that
I
(
xy
)=
I
(
uv
)=
I
.In
this case
G
necessarily has a chromosome of the form
(
... x v ... u y ...
)
or
(
... u y ... x v ...
)
. Therefore, there are at most two intervals of type 1 in
I
(
G
)
such that
I
I
(
G
)
.
Lemma 3.
The maximum number of intervals of type 2 in
I
(
G
)
is
n
.
Proof.
First, note that for two adjacencies
(
xy
)
and
(
xz
)
in
G
that do not contain
marker
,if
(
xy
)
is of type 2 then
(
xz
)
cannot be of type 2. Now, there is only one
marker
u
such that
(
u
◦
)
is an adjacency of
G
.Let
(
uv
)
be the adjacency of
G
having
u
as first marker, then at most half of the intervals in
◦
I
(
G
)
−{
I
(
uv
)
}
can be of type
2. Therefore, there are at most
n
intervals of type 2 in
I
(
G
)
.
Theorem 2.
If
NG
(
G
)
contains
C
cycles, then the BI single tandem halving distance of
G
is given by:
d
t
BI
(
G
)=
n
−
C
2
Proof.
Since there are
2
n
(
G
)
,andatmost
n
+2
are of type
1
or
2
,
then if
G
is a genome containing more than three distinct markers
n>
3
,then
2
n
−
1
intervals in
I
−
1
>n
+2
and there exist two compatible intervals in
I
(
G
)
inducing a BI
operation that decreases the DCJ distance by
2
.
Search WWH ::
Custom Search