Longtemps considéré comme une structure stable hautement optimisée, le génome des procaryotes nous apparaît, au regard de récentes découvertes, comme extrêmement changeant au cours du temps. Chez certaines bactéries, les gènes acquis récemment d'espèces distantes par transmission horizontale sont estimés à plus de 15 % du génome et les phylogénies construites à partir de différents gènes présentent fréquemment des incongruences importantes. De ce point de vue, la cohérence interne des génomes et la durabilité des interactions entre gènes au cours des temps évolutifs sont mises en question. Certains auteurs proposent que les transferts horizontaux se produisent à une fréquence telle que le concept même d'histoire des espèces ne s'applique pas aux procaryotes. Cependant, il a été suggéré que certaines catégories de gènes pouvaient être plus ou moins sensibles au transfert. Nous avons testé cette hypothèse au moyen de méthodes phylogénétiques et tenté de reconstruire une phylogénie des procaryotes en utilisant les génomes complets. Les résultats suggèrent que certains gènes conservent une information congruente sur l'histoire des bactéries et que la combinaison de ces informations peut permettre de reconstruire une phylogénie des bactéries. La nature des gènes détectés comme ayant été acquis récemment pose également problème. En effet, plusieurs auteurs ont remarqué que ces gènes avaient tendance à être enrichis en nucléotides A et T en comparaison du reste du génome. Nous avons analysé la structuration en nucléotides de nombreux génomes complets et montré que certaines caractéristiques intrinsèques aux génomes pourraient, dans certains cas, conduire à une surestimation de la quantité de gènes acquis par transferts horizontaux. Si d'un point de vue qualitatif, l'importance des transferts horizontaux dans l'évolution des procaryotes a été amplement démontrée, nous pensons qu'elle a été surestimée du point de vue quantitatif du fait de problèmes méthodologiques. Détectés par une méthode phylogénétique, les gènes récemment acquis montrent des caractéristiques qui les rapprochent de séquences parasites (phages notamment) ou non fonctionnelles, suggérant que certaines catégories de gènes pourraient être « spécialisées » dans le transfert horizontal.

L'inférence phylogénomique cherche à combiner le signal évolutif induit par un ensemble de gènes dans le but de construire un unique arbre phylogénétique.<br />Elle peut être décomposée en trois grandes familles méthodologiques: la combinaison basse, qui s'appuie sur la concaténation des différents gènes, la combinaison haute, qui considère l'ensemble des arbres inférés à partir de chaque gène, et la combinaison moyenne, qui encode les différents signaux phylogénétiques puis combine ces différents encodages.<br />Une méthode d'inférence d'arbre est ensuite appliquée sur le résultat de la combinaison.<br /><br />Cette thèse développe de nouveaux scénarios d'inférence phylogénomique, principalement basés sur l'estimation de distances évolutives entre chaque paire de taxons.<br />Elle propose une nouvelle méthode de combinaison moyenne, nommée SDM, qui considère les matrices de distance estimées à partir de chaque gène et qui les combine en une unique supermatrice de distance.<br />Cette dernière pouvant parfois contenir des distances manquantes, cette thèse décrit également de nouveaux algorithmes, nommés NJ*, UNJ*, BioNJ* et MVR*, permettant d'inférer très rapidement un arbre à partir d'une matrice de distance complète ou incomplète.<br />De nombreuses simulations ont permis d'observer les bonnes performances de ces nouvelles méthodes de distance.<br />Initialement développées pour la combinaison moyenne, elles permettent toutefois d'améliorer significativement les résultats de certaines approches standards en combinaison basse, et représentent une alternative efficace à MRP, la plus utilisée des techniques de combinaison haute, en termes de fiabilité et de rapidité.<br />La taille des jeux de données phylogénomiques étant de plus en plus importante, les méthodes développées dans cette thèse constituent ainsi des outils de choix pour construire l'Arbre de la Vie.

Les gènes, qui servent à encoder les fonctions biologiques des êtres vivants, forment l'unité moléculaire de base de l'hérédité. Afin d'expliquer la diversité des espèces que l'on peut observer aujourd'hui, il est essentiel de comprendre comment les gènes évoluent. Pour ce faire, on doit recréer le passé en inférant leur phylogénie, c'est-à-dire un arbre de gènes qui représente les liens de parenté des régions codantes des vivants. Les méthodes classiques d'inférence phylogénétique ont été élaborées principalement pour construire des arbres d'espèces et ne se basent que sur les séquences d'ADN. Les gènes sont toutefois riches en information, et on commence à peine à voir apparaître des méthodes de reconstruction qui utilisent leurs propriétés spécifiques. Notamment, l'histoire d'une famille de gènes en terme de duplications et de pertes, obtenue par la réconciliation d'un arbre de gènes avec un arbre d'espèces, peut nous permettre de détecter des faiblesses au sein d'un arbre et de l'améliorer. Dans cette thèse, la réconciliation est appliquée à la construction et la correction d'arbres de gènes sous trois angles différents: 1) Nous abordons la problématique de résoudre un arbre de gènes non-binaire. En particulier, nous présentons un algorithme en temps linéaire qui résout une polytomie en se basant sur la réconciliation. 2) Nous proposons une nouvelle approche de correction d'arbres de gènes par les relations d'orthologie et paralogie. Des algorithmes en temps polynomial sont présentés pour les problèmes suivants: corriger un arbre de gènes afin qu'il contienne un ensemble d'orthologues donné, et valider un ensemble de relations partielles d'orthologie et paralogie. 3) Nous montrons comment la réconciliation peut servir à "combiner'' plusieurs arbres de gènes. Plus précisément, nous étudions le problème de choisir un superarbre de gènes selon son coût de réconciliation. / Genes encode the biological functions of all living organisms and are the basic molecular units of heredity. In order to explain the diversity of species that can be observed today, it is essential to understand how genes evolve. To do this, the past has to be recreated by inferring their phylogeny, i.e. a gene tree depicting the parental relationships between the coding regions of living beings. Traditional phylogenetic inference methods have been developed primarily to construct species trees and are solely based on DNA sequences. Genes, however, are rich in information and only a few known reconstruction methods make usage of their specific properties. In particular, the history of a gene family in terms of duplications and losses, obtained by the reconciliation of a gene tree with a tree species, may allow us to detect weaknesses in a tree and improve it. In this thesis, reconciliation is applied to the construction and correction of gene trees from three different angles: 1) We address the problem of resolving a non-binary gene tree. In particular, we present a linear time algorithm that solves a polytomy based on reconciliation. 2) We propose a new gene tree correction approach based on orthology and paralogy relations. Polynomial-time algorithms are presented for the following problems: modify a gene tree so that it contains a given set of orthologous genes, and validate a set of partial orthology and paralogy relations. 3) We show how reconciliation can be used to "combine'' multiple gene trees. Specifically, we study the problem of choosing a gene supertree based on its reconciliation cost.