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.
|