En bioinformatique, un des problèmes très étudiés est la reconstitution des événements évolutifs qui transforment un génome A en un autre génome B. L'ordre des gènes dans les génomes est souvent modélisé par des permutations signées. Dans ce travail, nous définissons des liens entre le problème de tri des permutations signées par inversions et la conservation des structures combinatoires communes aux génomes à comparer. En utilisant les arbres des intervalles forts (Bergeron et al. (3)), nous démontrons que même si le calcul d'un scénario parfait et parcimonieux est difficile (Figeac et Varré (11)), il peut se faire d'une façon efficace pour une grande classe de permutations. Nous avons appliqué ces résultats à la comparaison des chromosomes X de l'humain, de la souris et du rat, basée sur les données de l'article de Gibbs et al. (12). ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Génomique comparée, Scénarios d'évolution, Tri par inversions, Intervalles communs.

Le but principal de ce travail est d'apporter une synthèse des travaux effectués sur les algorithmes capables d'identifier des groupes de gènes, ou des segments de génomes, communs à différentes espèces. Nous nous limitons à une approche basée sur la modélisation des génomes à l'aide de permutations, où les groupes d'éléments conservés entre différents génomes sont définis par la notion d'intervalles communs. L'étude approfondie de cette problématique nous a aussi permis d'innover et de présenter un nouvel algorithme plus général. Ce travail comporte donc deux aspects principaux, bien que le second soit intercalé dans le premier : une partie synthèse et une partie innovatrice. Après un survol des notions de bases, la partie synthèse présente les premiers algorithmes qui permettent de calculer les intervalles communs, puis l'approche de Bergeron et al. (2005) qui a grandement simplifié les premières solutions. Cette partie comprend aussi les algorithmes des mêmes auteurs qui calculent les intervalles communs dits forts, et une discussion sur les avantages de leur utilisation par rapport aux intervalles communs classiques. La partie innovatrice présente un nouvel algorithme qui généralise deux algorithmes de Bergeron et al. (2005). Nous concluons cette étude en constatant l'extrême simplicité et la grande efficacité, autant théorique que pratique, des plus récents algorithmes et nous croyons peu vraisemblable qu'il soit possible d'en améliorer la performance de façon significative. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Algorithmique, Génomique comparée, Intervalles communs, Permutations.

La génomique comparative étudie les similarités et/ou les dissimilarités entre génomes et permet d'établir des relations entre les espèces afin notamment de construire des phylogénies. Elle permet également de mettre en évidence des régions conservées au sein des génomes et de trouver ainsi des ensembles de gènes impliqués dans des processus biologiques conservés au cours de l'évolution. Dans ce mémoire, nous nous intéressons au calcul de mesures entre deux génomes en présence de gènes dupliqués, et plus particulièrement aux mesures à base de points de cassure, d'adjacences, d'intervalles communs et d'intervalles conservés. Suivant une démarche informatique, nous proposons tout d'abord une étude avancée de la complexité algorithmique des problèmes rencontrés, en prouvant notamment pour la plupart d'entre eux soit leur NP-Complétude soit leur APX-Difficulté. Par la suite, nous exposons plusieurs méthodes de calcul de mesures entre deux génomes, à savoir (i) une approche exacte basée sur une transformation en un problème de contraintes à variables booléennes, (ii) une heuristique et (iii) une méthode hybride qui s'appuie sur la méthode exacte et l'heuristique proposées. Par une étude sur un jeu de données réel, nous montrons les qualités respectives de ces méthodes. Enfin, nous proposons un protocole de calcul des intervalles communs et mettons en évidence, par son utilisation et par un outil de visualisation, l'aspect fonctionnel de certains intervalles communs.