title: Genome halving and double distance with losses.
abstract: Given a phylogenetic tree involving whole genome duplication events, we contribute to solving the problem of computing the rearrangement and double cut-and-join (DCJ) distances on a branch of the 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, called the double distance. Two algorithms are developed in both cases of a genome G containing exactly two copies of each gene, or at most two copies of each gene (with missing gene copies). These algorithms are shown time-efficient and very accurate for both the rearrangement and DCJ distances.
authors: DIRO, Université de Montréal, Montréal, Quebec, Canada. olivier.tremblay-savard@umontreal.ca
authors: Olivier Tremblay
authors: OT
authors: Savard
authors: Yves
authors: Y
authors: Gagnon
authors: Denis
authors: D
authors: Bertrand
authors: Nadia
authors: N
authors: El-Mabrouk
mesh_terms: D000465:Algorithms; D002875:Chromosomes / Q000235:genetics; D003198:Computer Simulation; D019143:Evolution, Molecular; D018628:Gene Dosage; D020440:Gene Duplication; D015321:Gene Rearrangement; D016678:Genome; D008957:Models, Genetic; D009154:Mutation; D010802:Phylogeny; D011003:Ploidies