• Calendar

March 4, Tuesday
12:00 – 14:00

A new problem in phylogenetic inference is presented, based on recent biological findings indicating a strong association between reversals 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 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). For that, a new data structure - namely set-tries - is presented, and is shown to support efficient linear-time insert and find operations. Joint work with Michal Ziv-Ukelson and Ron Pinter. The presentation is self contained.