An Algebraic Model for Sorting by Transpositions

Tzvika Hartman, Bar Ilan University

In this talk we discuss the problems of sorting signed permutations by reversals (SBR) and sorting unsigned permutations by transpositions (SBT), which are fundamental problems in computational molecular biology. While a polynomial-time solution for SBR is known, SBT has been open for more than a decade and is considered a major open problem. We outline a novel combinatorial framework for exploring SBT, and introduce a graphical model which is analogous to the interleaving graph of the Hannenhalli-Pevzner Theory for SBR. We further generalize this model, and connect it to an algebraic question about matrices over rings. We discover that this general model is in fact a common framework for both SBR and SBT (and other rearrangement problems). This model gives deep insight on these problems and sheds new light on old results. We are thus left with a problem of combinatorial-algebraic nature which is fundamental to several genome rearrangement problems. We give a variety of results about this problem and pose many open problems.
Joint work with Elad Verbin.