On the repeat-annotated phylogenetic tree reconstruction problem.
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).
Swidan
Firas
F
Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel. swidanf@janelia.hhmi.org
Ziv-Ukelson
Michal
M
Pinter
Ron Y
RY
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*