Biomedical Engineering Reference
In-Depth Information
(
◦
1
U
2
V
3
◦
)
→
(
◦
1
V
3
◦
)(
U
2)
The second DCJ operation is the integration that produces the adjacency
(
U
3)
by
reintegrating the circular chromosome
(
U
2)
in the appropriate way:
(
◦
1
V
3
◦
)(
U
2
)
→
(
◦
1
V
2
U
3
◦
)
.
A
rearrangement scenario
between two genomes
A
and
B
is a sequence of rearrange-
ment operations allowing one to transform
A
into
B
.
Definition 4.
A
BI (resp. DCJ) scenario
is a rearrangement scenario composed of BI
(resp. DCJ) operations.
The length of a rearrangement scenario is the number of rearrangement operations com-
posing the scenario.
Definition 5.
The
BI (resp. DCJ) distance
between two genomes
A
and
B
, denoted by
d
BI
(
A, B
)
(resp.
d
DCJ
(
A, B
)
), is the minimal length of a BI (resp. DCJ) scenario
between
A
and
B
.
2.3
Single Tandem Halving
We now state the single tandem halving problem considered in this paper.
Definition 6.
Given a totally duplicated genome
G
composed of a single linear chro-
mosome, the
BI single tandem halving problem
consists in finding a single tandem
duplicated genome
H
such that the BI distance between
G
and
H
is minimal.
In order to solve the BI single tandem halving problem, we use some results on the
DCJ
genome halving problem
that were stated in [9] as a starting point. However, unlike the
single tandem halving problem, the aim of the genome halving problem is to find a
perfectly duplicated genome instead of a single tandem duplicated genome.
Definition 7.
Given a totally duplicated genome
G
,the
DCJ genome halving problem
consists in finding a perfectly duplicated genome
H
such that the DCJ distance between
G
and
H
is minimal.
The BI and DCJ genome halving problems lead to two definitions of
halving distances
:
the
BI single tandem halving distance
(resp.
DCJ genome halving distance
) of a totally
duplicated genome
G
is the minimum BI (resp. DCJ) distance between
G
and any single
tandem duplicated genome (resp. any perfectly duplicated genome) ; we denote it by
d
t
BI
(
G
)
(resp.
d
p
DCJ
(
G
)
).
3
Lowerbound for the BI Single Tandem Halving Distance
In this section we give a lowerbound on the BI single tandem halving distance of a
totally duplicated genome. We use a data structure representing the genome called the
natural graph
introduced in [9].
Search WWH ::
Custom Search