Advertisement
Published in:
2010 | OriginalPaper | Chapter
Advances on Genome Duplication Distances
Authors : Yves Gagnon, Olivier Tremblay Savard, Denis Bertrand, Nadia El-Mabrouk
Published in: Comparative Genomics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a phylogenetic tree involving Whole Genome Duplication events, we contribute to the problem of computing the rearrangement distance on a branch of a tree linking a duplication node
d
to a speciation node or a leaf
s
. In the case of a genome
G
at
s
containing exactly two copies of each gene, the
genome halving problem
is to find a perfectly duplicated genome
D
at
d
minimizing the rearrangement distance with
G
. We generalize the existing exact linear-time algorithm for genome halving to the case of a genome
G
with missing gene copies. In the case of a known ancestral duplicated genome
D
, we develop a greedy approach for computing the distance between
G
and
D
that is shown time-efficient and very accurate for both the rearrangement and DCJ distances.