Ordre et désordre dans l’algorithmique du génome

Dans cette these, nous explorons la complexite algorithmique de plusieurs problemes issus de la genomique comparative, et nous apportons des solutions a certains de ces problemes sous la forme d’algorithmes d’approximation ou parametres. Le denominateur commun aux problemes souleves est la mise en commun d’informations genomiques provenant de plusieurs especes dans le but de tirer des conclusions pertinentes pour l’etude de ces especes. Les problemes de tri par transpositions et de tri par inversions prefixes permettent de retrouver l’histoire evolutive des deux especes. Les problemes de distance exemplaire et de plus petite partition commune ont pour but de comparer deux genomes dans les cas algorithmiquement difficiles ou chaque gene apparait avec plusieurs copies indistinguables dans le genome. Enfin, les problemes d’extraction de bandes et de linearisation visent a preciser ou corriger l’information genomique afin qu’elle soit plus pertinente pour des traitements ulterieurs. Les resultats principaux que nous presentons sont la NP-difficulte des problemes de tri (par transpositions et par inversions prefixes) dont la complexite est restee longtemps une question ouverte; une etude complete de la complexite du calcul des distances exemplaires; un algorithme parametre pour le calcul de plus petite partition commune (avec un unique parametre etant la taille de la partition); une etude a la fois large et approfondie des problemes d’extraction de bandes et enfin une nouvelle structure de donnees permettant de resoudre plus efficacement le probleme de linearisation.