Pavel A. Pevzner, Pennsylvania State Univ.

Rearrangements of maps, sequences and genomes

I discuss Schmitt-Waterman's conjecture about cassette transformations of physical maps (motivated by 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.