ABSTRACT:

Finding the distance between two genomes is a key problem in computational
biology. The two main approaches for it are edit distance, which leads to
an analysis of point mutations, or genome rearrangements, allowing for a
much broader view of the changes that may have evolved one genome into
another. In this talk we will focus exclusively on the second approach,
showing some of the major achievements that have been made in this area
since its inception.

We will begin this talk by presenting the motivation and basic definitions
for the problem: genomes, chromosomes, genes, rearrangement events and
distance based on such events. The computational complexity of some
rearrangement problems is going to be presented and, in the end, a "novel"
measure inspired by the solution for the general problem of sorting by
translocations, inversions and block-interchanges is discussed.
Rodrigo Hausen is a Ph.D. student at COPPE Sistemas/UFRJ, Brazil and is a guest
researcher at the Lab. for Innovation in Bioinformatics advised by Prof. David
Sankoff.