מיכל זיו-יוקלסון

A new problem in phylogenetic inference is presented, based on recent biological findings indicating a strong association between reversals (aka inversions) and repeats. These biological findings are formalized here in a new mathematical model, called repeat-annotated phyImjenetic 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 practico. 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).