I discuss Schmitt-Waterman conjecture about cassette transformations of physical maps (motivated by double digest DNA physical mapping), Ukkonen's conjecture about equivalent transformations of texts (motivated by DNA sequencing by hybridization) and Gollan's conjecture about the reversal diameter of the symmetric group (motivated by genome rearrangements). Surprisingly enough, similar combinatorial techniques (alternating cycles in edge-coloured graphs) prove all three conjectures and provide a clue for algorithms in such diverse areas of computational biology as double digest physical mapping, sequencing by hybridization and genome rearrangements. If time allows I will describe the applications of these algorithms to analyze rearrangements of herpes viruses, plant organelles, and mammalian chromosomes.

The work on genome rearrangements is a joint project with Vineet Bafna (DIMACS), Colombe Chappey (NIH), Sridhar Hannenhalli (Penn State) and Eugene Koonin (NIH).

Program

DIMACS Homepage