title: On the repeat-annotated phylogenetic tree reconstruction problem.
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).
authors.affiliation: Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel. swidanf@janelia.hhmi.org
authors.forename: Firas
authors.initials: F
authors.lastname: Swidan
authors.forename: Michal
authors.initials: M
authors.lastname: Ziv-Ukelson
authors.forename: Ron Y
authors.initials: RY
authors.lastname: Pinter
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D016680:Genome, Bacterial / Q000235:genetics*; D008954:Models, Biological; D010802:Phylogeny; D011995:Recombination, Genetic / Q000235:genetics; D012091:Repetitive Sequences, Nucleic Acid / Q000235:genetics*