Finalist EPFL doctorate Award 2011 - Krister Swenson

Evolution of whole genomes through inversions : models and algorithms for duplicates, ancestors, and edit scenarios.

A problem rst posed by biologists in 1941, but rediscovered in the early eighties, was that of sorting by inversions: given two genomes, nd the minimum number of inversions to turn one into the other, where an in- version inverts the order of contiguous genes, making them readable now on the opposite strand. Aside from being an intriguing computer science question in its own right, it turns out that some genomes have evolved through mostly or only inversions. These distances have since been successfully used to automate phylogeny reconstruction.
An impressive theory has developed that allows us to calculate parsimonious inversion distances given a pair of genomes, along with an actual scenario of inversions to match the distance. However, certain assumptions have limited the applicability of these methods; in particular, most genomes may have undergone duplication, loss, and gain (such as in lat- eral gene transfer). In this dissertation I extend the theory so as to make these distances consider the full gambit of operations. Further, I give preliminary insight into conditions under which evolutionary ancestral states can be accurately calculated. Finally, I give a fast algorithm (at the theoretical limit) for nding a parsimonious evolutionary scenario of inversions.