Pavel Pevzner - Transforming mice into men

Many people (including myself) believe that transformationsof humans into mice happen only in fairy tales. However, despite some differences in appearance and habits, men and mice are genetically very similar. In the pioneering paper, Nadeau and Taylor, 1984 estimated that surprisingly few genomic rearrangements (approximately 180) happened since the divergence of human and mouse 80 million years ago. However, their analysis is non-constructive and no rearrangement scenario for human-mouse evolution has been suggested yet. The problem is complicated by the fact that rearrangements in multi-chromosomal genomes include inversions, translocations, fusions and fissions of chromosomes, a rather complex set of operations. As a result, at the first glance, a polynomial algorithm for the genomic distance problem with all these operations looks almost as improbable as the transformation of a (real) man into a (real) mouse. We prove a duality theorem which expresses the genomic distance in terms of easily computable parameters reflecting different combinatorial properties of sets of strings. This theorem leads to a polynomial-time algorithm for computing most parsimonious rearrangement scenarios. Based on this result and the latest comparative physical mapping data we have constructed a scenario of human-mouse evolution with 131reversals/translocations/fusions/fissions. A combination of the genome rearrangement algorithm with new experimental techniques for deriving gene orders suggests a new approach to the 100-year old problem of reconstructing mammalian evolution.

This is a joint work with Sridhar Hannenhalli.