On the repeat-annotated phylogenetic tree reconstruction problem. |
| |
Authors: | Firas Swidan Michal Ziv-Ukelson Ron Y Pinter |
| |
Affiliation: | Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel. swidanf@janelia.hhmi.org |
| |
Abstract: | A new problem in phylogenetic inference is presented, based on recent biological findings indicating a strong association between reversals (i.e., inversions) and repeats. These biological findings are formalized here in a new mathematical model, called repeat-annotated phylogenetic trees (RAPT). We show that, under RAPT, the evolutionary process--including both the tree-topology as well as internal node genome orders--is uniquely determined, a property that is of major significance both in theory and in practice. Furthermore, the repeats are employed to provide linear-time algorithms for reconstructing both the genomic orders and the phylogeny, which are NP-hard problems under the classical model of sorting by reversals (SBR). |
| |
Keywords: | |
|
|