DIMACS Seminar on Mathematics and Computer Science in Biology
Polynomial algorithm for sorting signed permutations by reversals
- Sridhar Hannenhalli
- Department of Computer Science and Engineering, Pennsylvania State Univ.
- Seminar Room 431, CoRE Building,
- Busch Campus, Rutgers University.
- 3 PM - 4 PM
- Monday, February 13, 1995
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
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.
Feb 20: Dr. Richard Lipton (at Princeton U.)
Document last modified on February 9, 1995