L'augmentation du nombre de génomes totalement séquencés rend de plus en plus efficace l'étude des mécanismes évolutifs à partir de la comparaison de génomes contemporains. L'un des principaux problèmes réside dans la reconstruction d'architectures de génomes ancestraux plausibles afin d'apporter des hypothèses à la fois sur l'histoire des génomes existants et sur les mécanismes de leur formation. Toutes les méthodes de reconstruction ancestrale ne convergent pas nécessairement vers les mêmes résultats mais sont toutes basées sur les trois mêmes étapes : l'identification des marqueurs communs dans les génomes contemporains, la construction de cartes comparatives des génomes, et la réconciliation de ces cartes en utilisant le critère de parcimonie maximum. La qualité importante des données à analyser nécessite l'automatisation des traitements et résoudre ces problèmes représente de formidables challenges computationnels. Affiner le modèles et outils mathématiques existants par l'ajout de contraintes biologiques fortes rend les hypothèses établies biologiquement plus réalistes. Dans cette thèse, nous proposons une nouvelle méthode permettant d'identifier des marqueurs communs pour des espèces évolutivement distantes. Ensuite, nous appliquons sur les cartes comparatives reconstituées une nouvelle méthode pour la reconstruction d'architectures ancestrales basée sur les adjacences entre les marqueurs calculés et les distances génomiques entre les génomes contemporains. Enfin, après avoir corrigé l'algorithme existant permettant de déterminer une séquence optimale de réarrangements qui se sont produits durant l'évolution des génomes existants depuis leur ancêtre commun, nous proposons un nouvel outil appelé VIRAGE qui permet la visualisation animée des scénarios de réarrangements entre les espèces / Abstract

L'augmentation du nombre de génomes totalement séquencés rend de plus en plus efficace l'étude des mécanismes évolutifs à partir de la comparaison de génomes contemporains. L'un des principaux problèmes réside dans la reconstruction d'architectures de génomes ancestraux plausibles afin d'apporter des hypothèses à la fois sur l'histoire des génomes existants et sur les mécanismes de leur formation. Toutes les méthodes de reconstruction ancestrale ne convergent pas nécessairement vers les mêmes résultats mais sont toutes basées sur les trois mêmes étapes : l'identification de marqueurs commun dans les génomes contemporains, la construction de cartes comparatives des génomes, et la réconciliation de ces cartes en utilisant le critère de parcimonie maximum. La quantité importante des données à analyser nécessite l'automatisation des traitements et résoudre ces problèmes représente de formidables challenges computationnels. Affiner les modèles et outils mathématiques existants par l'ajout de contraintes biologiques fortes rend les hypothèses établies biologiquement plus réalistes. Dans cette thèse, nous proposons une nouvelle méthode permettant d'identifier des marqueurs communs pour des espèces évolutivement distantes. Ensuite, nous appliquons sur les cartes comparatives reconstituées une nouvelle méthode pour la reconstruction d'architectures ancestrales basée sur les adjacences entre les marqueurs calculés et les distances génomiques entre les génomes contemporains. Enfin, après avoir corrigé l'algorithme existant permettant de déterminer une séquence optimale de réarrangements qui se sont produits durant l'évolution des génomes existants depuis leur ancêtre commun, nous proposons un nouvel outil appelé VIRAGE qui permet la visualisation animée des scénarios de réarrangements entre les espèces.

La duplication est un des évènements évolutifs les plus importants, car elle peut mener à la création de nouvelles fonctions géniques. Durant leur évolution, les génomes sont aussi affectés par des inversions, des translocations (incluant des fusions et fissions de chromosomes), des transpositions et des délétions. L'étude de l'évolution des génomes est importante, notamment pour mieux comprendre les mécanismes biologiques impliqués, les types d'évènements qui sont les plus fréquents et quels étaient les contenus en gènes des espèces ancestrales. Afin d'analyser ces différents aspects de l'évolution des génomes, des algorithmes efficaces doivent être créés pour inférer des génomes ancestraux, des histoires évolutives, des relations d'homologies et pour calculer les distances entre les génomes. Dans cette thèse, quatre projets reliés à l'étude et à l'analyse de l'évolution des génomes sont présentés : 1) Nous proposons deux algorithmes pour résoudre des problèmes reliés à la duplication de génome entier : un qui généralise le problème du genome halving aux pertes de gènes et un qui permet de calculer la double distance avec pertes. 2) Nous présentons une nouvelle méthode pour l'inférence d'histoires évolutives de groupes de gènes orthologues répétés en tandem. 3) Nous proposons une nouvelle approche basée sur la théorie des graphes pour inférer des gènes in-paralogues qui considère simultanément l'information provenant de différentes espèces afin de faire de meilleures prédictions. 4) Nous présentons une étude de l'histoire évolutive des gènes d'ARN de transfert chez 50 souches de Bacillus. / Gene duplication is one of the most important types of events affecting genomes during their evolution because it can create novel gene function. During the evolution process, genomes are also affected by inversions, translocations (including chromosome fusions and fissions), transpositions and deletions. Studying the evolution of genomes is important to get a better understanding of the biological mechanisms involved, which types of events are more frequent than others and what was the gene content in the ancestral species just to name a few. In order to analyze these different aspects of genome evolution, efficient algorithms need to be developed to infer ancestral genomes, evolutionary histories, homology relationships between genes and to compute distances between genomes. In this thesis, four different projects related to the study and analysis of genome evolution are presented: 1) We developed two algorithms to solve problems related to whole genome duplication: one that generalizes the genome halving problem to gene losses, and one that allows to compute the double distance with losses. 2) We developed a new method to infer evolutionary histories of orthologous tandemly arrayed gene clusters. 3) We proposed a new graph-theoretic approach to infer inparalogs that simultaneously considers the information given by multiple species in order to make better inferences of inparalogous gene pairs. 4) We studied the evolutionary history of the tRNA genes of 50 Bacillus strains.

Dans les génomes bactériens, les fréquents transferts horizontaux de gènes (HGT) introduisent des innovations génomiques qui peuvent entraîner la diversification des populations bactériennes. À l'inverse, la recombinaison homologue (RH) au sein des populations homogénéise leurs génotypes, et ainsi renforce leur cohésion. Ces processus d'échange génétique, et la fréquence à laquelle ils interviennent au sein et entre les populations, doivent avoir un grand impact sur la cladogénèse bactérienne. Au-delà de la configuration des échanges qui se sont réellement produits entre les bactéries, les traces de RH et de HGT que nous observons dans leurs génomes reflètent les événements qui ont été fixés tout au long de leur histoire. Ce processus de fixation peut être biaisé en ce qui concerne la nature des gènes ou allèles qui ont été introduits. La sélection naturelle peut notamment conduire à la fixation des gènes transférés qui apportent de nouvelles adaptations écologiques. En outre, des biais mécaniques dans le processus de recombinaison lui-même peuvent conduire à la fixation d'allèles non-adaptatifs. Nous avons cherché à caractériser certains de ces processus adaptatifs et non-adaptatifs qui façonnent les génomes bactériens. À cette fin, plusieurs aspects de l'évolution des génomes, comme les variations de leurs répertoires de gènes, de leur architecture et de leur composition en nucléotides ont été examinés à la lumière de leur histoire de transfert et de recombinaison / In bacterial genomes, the frequent horizontal gene transfers (HGT) introduce genomic novelties that can promote the diversification of bacterial populations. In opposition, homologous recombination (HR) within populations homogenizes their genotypes, enforcing their cohesion. These processes of genetic exchange, and their patterns of occurrence among and within lineages, must have a great impact on bacterial cladogenesis. Beyond the pattern of exchanges actually occurring between bacteria, the traces of HR and HGT we observe in their genomes reflect what events were fixed throughout their history. This fixation process can be biased regarding the nature of genes or alleles that were introduced. Notably, natural selection can drive the fixation of transferred genes that bring new ecological adaptations. In addition, some mechanical biases in the recombination process itself may lead to the fixation of non-adaptive alleles. We aimed to characterize such adaptive and non-adaptive processes that are shaping bacterial genomes. To this end, several aspects of genome evolution, such as variations of their gene repertoires, of their architecture and of their nucleotide composition were examined in the light of their history of transfer and recombination