DIMACS Seminar on Mathematics and Computer Science in Biology

Title:

Polynomial algorithm for sorting signed permutations by reversals

Speaker:

Sridhar Hannenhalli

Department of Computer Science and Engineering, Pennsylvania State Univ.

Place:

Seminar Room 431, CoRE Building,

Busch Campus, Rutgers University.

Time:

3 PM - 4 PM

Monday, February 13, 1995

Abstract:

Analysis of genome rearrangements in molecular biology started in the late 1930's, when Dobzhansky and Sturtevant published a milestone paper presenting a rearrangement scenario with 17 inversions for the species of Drosophila. Analysis of genomes evolving by inversions leads to a combinatorial problem of "sorting by reversals" studied in detail recently. Kececioglu and Sankoff conjectured that sorting by reversals s NP-hard, but despite many attempts their conjecture remains open. We study sorting of "signed" permutations by reversals, a problem which adequately models rearrangements in small genomes like chloroplast or mitochondrial DNA. The previously suggested performance guarantee algorithms for sorting signed permutations by reversals approximate the reversal distance between permutations with an astonishing accuracy for both simulated and biological data. We prove a duality theorem explaining this intriguing performance and show that there exists a "hidden" parameter which allows one to efficiently compute the reversal distance between signed permutations.

footnote: This is a joint work with Pavel Pevzner

General Announcement:

Please note that this semester we plan to hold the seminar at different places including the DIMACS seminar room, the Waksman institute, U. Penn and Princeton, so be sure to check the venue.

As before, the seminar will be held Mondays 3-4pm, unless a special year workshop or lecture is scheduled for that date.

Future talks:

Feb 20: Dr. Richard Lipton (at Princeton U.)

Document last modified on February 9, 1995