Loading...
Please wait, while we are loading the content...
Similar Documents
Genome Halving and Double Distance with Losses
| Content Provider | CiteSeerX |
|---|---|
| Author | El-Mabrouk, Nadia Savard, Olivier Tremblay Bertr, Denis Gagnon, Yves |
| Abstract | Abstract. Given a phylogenetic tree involving Whole Genome Duplication events, we contribute to solving the problem of computing the rearrangement and 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. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Double Distance Duplication Node Rearrangement Distance Speciation Node Whole Genome Duplication Event Greedy Approach Phylogenetic Tree Dcj Distance Genome Halving Problem Genome Halving Gene Copy Exact Linear-time Algorithm |
| Content Type | Text |
| Resource Type | Article |
