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