Anne BERGERON, Université du Québec, Montréal, Canada.

"Similarity vs. Distance in Whole Genome Comparison"

The simplest problems of combinatorial genome comparison are the distance problems: given two genomes and a set of allowable rearrangement operations, what is the minimum number of operations needed to transform one genome into the other one. The minimalist beauty of these problems attracted generations of eager computer scientists who, sometimes, provided very elegant solutions. But then came the doubtful biologists insisting that, for any proposed rearrangement scenario, life must still go on at every step of the process. For example, scenarios that destroy, and later restore, common features of two genomes in order to transform one into the other are highly suspicious. In this talk, we will discuss the role of invariants -- or conserved structures -- in rearrangement scenarios, and we will show that sometimes, both the biologists and the minimalists agree.