Algorithmic Aspects of Genome Rearrangements

In this thesis, we explore the algorithmical complexity of several problems stemming from comparative genomics, and we provide solutions for some of these problems in the form of parameterized or approximation algorithms. The problems we consider have for common denominator to bring together the genomic information of several species with the objective of drawing relevant conclusions for the study of these species. The problems of sorting a genome by transpositions or by pre x reversals lead to the reconstruction of the evolution history of two species genomes. Exemplar distances and common partition aim at comparing genomes in the algorithmicaly complex case where duplicated genes are present. Finally, the strip recovery and linearization problems aim at correcting or completing genomic information so that it can be used for further analysis. The main results we expose are the NP-hardness of the sorting problems (both by transpositions and by pre x reversals), of which the computational complexity has been a long-standing open question; an exhaustive study of the computational complexity of exemplar distances; a parameterized algorithm for the minimum common string partition problem; a deep and wide study of strip recovery problems; and nally a new graph structure allowing for a more e cient solving of the linearization problem.