Events

Matrix Tightness: A Linear-Algebraic Framework for Sorting by Transpositions

00:00 26-04-2006

In this talk we study 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.

Add to calendar

Outlook

Google

Back to Home

Events

Matrix Tightness: A Linear-Algebraic Framework for Sorting by Transpositions

About HIT

Faculties & Departments

Undergraduate Programs

Graduate Programs

Quick links