Genome halving and double distance with losses |
| |
Authors: | Savard Olivier Tremblay Gagnon Yves Bertrand Denis El-Mabrouk Nadia |
| |
Institution: | DIRO, Université de Montréal, Montréal, Quebec, Canada. olivier.tremblay-savard@umontreal.ca |
| |
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. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|