L'émergence des expériences dites à haut débit permet l'acquisition rapide de données concernant un système biologique. Les biologistes disposent ainsi, aujourd'hui, d'un nombre important de données de natures hétérogènes qu'ils cherchent à structurer et analyser. Les méthodes dites intégratives proposent de répondre à cette demande, mais la création d'une méthode générale et satisfaisant les requêtes précises des biologistes constitue une tâche ardue. Ce mémoire s'inscrit dans cette problématique. Nous y abordons diverses méthodes d'intégration des aspects omiques (métaboliques, génomiques, transcriptomiques...) d'un système bactérien et nous proposons la nôtre, nommée SIPPER, qui est une méthode générique et flexible. SIPPER permet de retrouver de l'information biologique cohérente entre les différents aspects étudiés grâce à la construction d'un modèle intégratif et l'utilisation d'une distance reposant sur des propriétés ou hypothèses biologiques choisies. Nous avons appliqué SIPPER deux fois sur les données métaboliques et génomiques d'E. coli. La première application teste l'hypothèse "les chaînes de réactions successives du réseau métabolique sont catalysées à l'aide d'enzymes produites par des gènes proches sur le génome", et la seconde teste l'hypothèse "les chaînes de réactions successives sont catalysées par des gènes dont l'expression est similaire". Nous avons découvert, par ces expériences, des mesures caractérisant certaines entités biologiques comme la densité génomique qui permet l'identification d'opérons métaboliques. L'apport de l'intégration de données supplémentaires aux approches n'utilisant traditionnellement qu'un seul type d'information a également été illustré au travers de la génomique comparative. Nous avons ainsi élaboré M&W-IISCS_M, une méthode qui calcule des intervalles communs maximaux ayant un fort intérêt omique.

Les bactéries pectinolytiques des genres Pectobacterium (ancien nom Erwinia carotovora) et Dickeya (ancien nom Erwinia chrysanthemi) sont les agents des maladies de la jambe noire et de la pourriture molle. Ils provoquent des dommages aux cultures et des pertes économiques élevées. Les pertes causées par les bactéries pectinolytiques sont évaluées à environ 2 à 10% du rendement de pommes de terre, en fonction de l'année. En 2009, les pertes en pommes de terre en Europe ont été estimées à 250 millions d'euros. Au cours des dernières années, des souches de Dickeya ont été de plus en plus souvent isolées de plantes malades en Pologne, en France et d'autres pays européens. Le genre Dickeya est un groupe très diversifié, qui, selon la nomenclature actuelle contient sept espèces: D. aquatica, D. chrysanthemi, D. dadantii, D. dianthicola, D. paradisiaca, D. solani et D. zeae. Les résultats récents, obtenus dans différents pays européens, indiquent qu'un nouveau groupe de souches de Dickeya peut infecter efficacement les plantes de pomme de terre et causer des symptômes de la maladie en climat tempéré. Les souches de D. solani sont considérés comme plus agressives que les autres bactéries causant la jambe noire. Une analyse préliminaire a suggéré qu’elles ont besoin de plus faibles températures optimales pour le développement de la maladie ainsi que de niveaux d'inoculum inférieurs pour la propagation de l'infection. Elles semblent avoir une plus forte capacité à coloniser les racines de plantes de pomme de terre et à se propager à travers le système vasculaire de la plante. Les souches de D. solani produisent une large gamme d’enzymes dégradant de la paroi cellulaire végétale, qui sont les principaux facteurs de virulence. Les objectifs de l'étude étaient les suivants: 1) la caractérisation phénotypique et génotypique des souches de D. solani isolées dans des pays ayant des conditions climatiques différentes: Pologne, Finlande et Israël, 2) l'étude de l’influence d'extraits de pomme de terre sur l'expression de quelques gènes sélectionnés de D. solani: pelD, pelL, tssk, lfaA, 3) la génomique comparative de dix souches de D. solani, basée sur 4 génomes séquencés pour cette étude et 6 séquences génomiques disponibles dans la base de données GenBank. En conclusion, toutes les études génomiques ont montré que les souches de D. solani forment un groupe très homogène. Cependant, leur analyse phénotypique révèle une certaine variabilité entre les souches provenant de différentes conditions climatiques. La raison des variations observées dans les traits phénotypiques peut être liée à la régulation de l'expression des gènes codant les facteurs de virulence qui peuvent être influencés par la température, le pH, la carence en fer ou en oxygène et la disponibilité en azote, ainsi que par la présence de composés spécifiques des tissus végétaux. / Dickeya solani is a species consisting of newly emerged plant pathogenic bacteria that cause blackleg and soft rot diseases. They are responsible for great damages to potato plantations in most of European countries. D. solani strains produce a wide range of plant cell-wall degrading enzymes which are the main virulence factors. The aims of the study were: 1) phenotypic and genotypic characterizations of the D. solani strains isolated in countries with different climatic conditions: Poland, Finland and Israel, 2) study of the potato tuber extract influence on the expression of a few selected D. solani genes : pelD, pelL, tssK, lfaA,3) comparative genomics of ten D. solani strains, performed on 4 genomes sequenced for this study and 6 genome sequences available in the GenBank databases. The results showed that the strains from different climatic conditions have identical profiles in rep-PCR (with three different primers) and in Restriction Fragments Lenght Polymorphism-Pulse Field Gel Electrophoresis. However, they do differ phenotypically, especially in the activity of plant cell-wall degrading enzymes. Polish strains have higher activities of pectinolytic, cellulolytic and proteolytic enzymes than Finnish and Israeli strains. D. solani mutants in the pelD, pelL, tssK, lfaA genes were constructed by site-specific mutagenesis. The highest induction by plant extracts was observed for the lfaA gene. The expression of pelL is also induced by plant derived signal(s), but not that of pelD and tssK. Comparative genomics helped to elucidate the D. solani pangenome. The 10 D. solani strains genomes are coding for a total of 41 947 proteins which were grouped into 5 045 Orthologous Groups, 3 809 belonging to the core genome, 413 to the accessory genome and 823 to the unique genome. Some pathogenicity-related genes as well as their regulators were selected on the basis of the knowledge available for D. dadantii 3937, the most studied Dickeya strain, which belongs to a closely related species. Analysis of their protein sequence showed no difference in the sequence of those genes within the 10 genomes. All the genetic studies proved that D. solani strains form a very homogenous group. On the other hand, the phenotypic analysis showed some variability among strains from different climatic conditions. The observed variations in the phenotypic traits can results from a different regulation of the expression of the genes encoding virulence factors which are influenced by temperature, pH, iron deprivation, oxygen and nitrogen availability, as well as by the presence of plant compounds.

Mon projet de doctorat était de créer un pipeline pour taxono-génomique pour la comparaison de plusieurs génomes bactériens. Deuxièmement, je automatisé le processus d'assemblage (NGS) et annotation à l'aide de divers logiciels open source ainsi que la création de scripts de maison pour le laboratoire. Enfin, nous avons intégré le pipeline dans la description de plusieurs espèces bactériennes de laboratoire sur. Cette thèse est divisée principalement en Taxono- génomique et Microbiogenomics. Les avis de la section taxono-génomique, décrit sur les avancées technologiques en génomique et métagénomique pertinentes dans le domaine de la microbiologie médicale et décrit la stratégie taxono-génomique en détail et comment la stratégie polyphasique avec des approches génomiques sont reformatage de la définition de la taxonomie bactérienne. Les articles décrivent les bactéries cliniquement importantes, leur séquençage complet du génome et les études génomiques comparatives, génomiques et taxono-génomique de ces bactéries. Dans cette thèse, j'ai inclus les articles décrivant ces organismes: Megasphaera massiliensis, Corynebacterium ihumii, Collinsella massiliensis, Clostridium dakarense. Bacillus dielmoensis, jeddahense, Occidentia Massiliensis, Necropsobacter rosorum et Pantoea septica. Oceanobacillus / My PhD project was to create a pipeline for taxono-genomics for the comparison of multiple bacterial genomes. Secondly I automated the process of assembly (NGS) and annotation using various open source softwares as well as creating in house scripts for the lab. Finally we incorporated the pipeline in describing several bacterial species from out lab. This thesis is subdivided mainly into Taxono-genomics and Microbiogenomics. The reviews in taxono-genomics section, describes about the technological advances in genomics and metagenomics relevant to the field of medical microbiology and describes the strategy taxono-genomics in detail and how polyphasic strategy along with genomic approaches are reformatting the definition of bacterial taxonomy. The articles describes clinically important bacteria, their whole genome sequencing and the genomic, comparative genomic and taxono-genomic studies of these bacteria.

La première partie de nos travaux a consisté au séquençage de génomes complets de trois souches pathogènes et de trois souches de portage de Staphylococcus lugdunensis pour les comparer aux 15 génomes complets disponibles sur NCBI. Aucun déterminant génétique associé au contexte de virulence ou de portage de S. lugdunensis n’a été identifié. Cependant, nous avons mis en évidence la présence d’éléments génétiques mobiles et des variations dépendantes des complexes clonaux,définis par MultiLocus Sequence Typing, au sein de loci potentiellement associés à la virulence. Des variations ont été observées dans un locus homologue à celui de Staphylococcus aureus codant le système de sécrétion Ess/type VII (SST7). Nous avons mis en évidence huit organisations génétiques chez cette espèce présentant pourtant une structure de population clonale. La seconde partie de nos travaux a consisté à la caractérisation phénotypique et moléculaire du SST7 chez S. lugdunensis par la formation d’un mutant de délétion du gène essC codant une protéine essentielle à la sécrétion. Nos résultats suggèrent que le SST7 serait impliqué dans la translocation de protéines prédites in silico comme impliquées dans la virulence. Néanmoins, dans des modèles de cytotoxicité cellulaire et d’infection du nématode Caenorhabditis elegans, aucune atténuation de la virulence n’a été observée chez la souche mutante malgré une perte de sa capacité à lyser les erythrocytes, comparativement à la souche sauvage. Nos travaux ont également permis de développer et d’évaluer le pouvoir discriminant de trois nouvelles méthodes de typage constituant des outils très prometteurs pour l’épidémiologie moléculaire des infections à S. lugdunensis. / The first part of this study consisted in whole genome sequencing of three pathogenic and three carriage strains of S. lugdunensis and comparison with the 15 genomes available in the NCBI. No genetic determinant was associated to the pathogenic or carriage context. However, we have highlighted the presence of mobile genetic elements and MultiLocus Sequence Typing clonal complex dependent variations within loci potentially associated with virulence. Variations wereobserved in the ess locus homologous to that of Staphylococcus aureus encoding the type VII secretion system (T7SS). We showed eight genetic organizations in this species with a clonal population structure. The second part of our work consisted in a phenotypic and molecular characterization of T7SS in S. lugdunensis by construction of a deletion essC gene mutant. This gene encodes a protein requiredfor protein secretion. Our results suggest that T7SS could be involved in translocation of proteins predicted as implicated in virulence in silico. Nevertheless, no virulence attenuation was observed in cells cytotoxicity assay and Caenorhabditis elegans virulence assays between wild-type and mutant strains which yet has lost the ability to lyse erythrocytes. We also developed and evaluated discriminating power of three new typing methods, which are very promising tools for the molecular epidemiology of S. lugdunensis infections.

Virtuellement toutes les plantes hébergent des champignons et des bactéries endosymbiontes (endophytes). Ces microorganismes façonnent le développement de leur hôte et peuvent inhiber des phytopathogènes. Au niveau moléculaire, les interactions plante-endophyte sont médiées par des molécules secrétées y compris des protéines et métabolites secondaires. Au cours des dernières années, la recherche d’endophytes a augmenté chez nombreux plantes, cependant chez les Ericaceae les endophytes ne sont pas bien connus. Alors, on s’est mis à investiguer les endophytes racinaires de la canneberge, une plante membre d’Ericaceae native de l’Amérique du Nord. On a échantillonné quatre plants provenant d’une ferme commerciale organique. Au total, 30 souches fongiques et 25 bactériens ont été isolés. Les bactéries Pseudomonas sp. EB212, Bacillus sp. EB213 et EB214; et les champignons Hyaloscypha sp. EC200, Pezicula sp. EC205 et Phialocephala sp. EC208 ont supprimé la croissance de cinq pathogènes de la canneberge, incluant Godronia cassandrae, un champignon causant la pourriture des fruits de la canneberge au Québec. EB213 a été capable de promouvoir légèrement la croissance de plantules de la canneberge. En performant des techniques microscopiques, on a constaté l’habileté de EC200, EC205 et EC208 à coloniser internement les racines des plantules de la canneberge. De plus, les génomes de ces champignons ont été séquencés, assemblés et annotés. Les analyses génomiques se sont concentrées sur les protéines secrétées et les groupes des gènes impliqués dans la biosynthèse (GGB). On a trouvé un large répertoire de gènes codant pour des enzymes qui métabolisent les carbohydrates et d’autres codant pour des protéases. Les deux groupes d’enzymes seraient utiles à dégrader de la matière organique pour libérer des nutriments. Aussi bien, ces enzymes pourraient faciliter la colonisation des racines de la plante hôte. De plus, on a prédit des nombreuses protéines effectrices qui assisteraient les endophytes à éviter l’activation du système immunitaire des plants. A noter que parmi les GGB inférés dans les génomes de EC200, EC205 et EC208, environ 90% ne sont pas caractérisés. Finalement, on a performé des analyses transcriptomiques pour élucider la réponse de EC200, EC205 et EC208 envers la présence de leur hôte, simulée par l’addition d’un extrait de canneberge au milieu de culture. Les conclusions majeures sont que les racines des plantes de la canneberge qui ont été échantillonnées sont dominées par des microorganismes avec l’habileté d’inhiber des phytopathogènes ; et que les génomes de EC200, EC205 et EC208 codent pour un grand répertoire de protéines qui pourraient être liées aux interactions plante-endophyte. / Virtually all plants host fungal and bacterial endosymbionts (endophytes). These microbes shape plant development and may inhibit phytopathogens. At the molecular level, plant-endophyte interactions are mediated by secreted compounds, including proteins and secondary metabolites. While endophytes are increasingly studied in diverse plants, little is known about their presence in Ericaceae. Therefore, we set out to investigate the root endophytes of cranberry, an ericacean member native to North America. We sampled endophytes from four plants grown on an organic farm. In total, 30 fungal and 25 bacterial strains were isolated and identified. A subset of these, notably Pseudomonas sp. EB212, Bacillus sp. EB213 and EB214; and fungi Hyaloscypha sp. EC200, Pezicula sp. EC205, and Phialocephala sp. EC208, were tested for their ability to suppress phytopathogens. Altogether, they inhibited five cranberry pathogens, including Godronia cassandrae, an important cranberry fruit-rot agent in Quebec. EB213 was the only endophyte that increased the biomass of cranberry seedlings. Using microscopy techniques, we confirmed the ability of EC200, EC205, and EC208 to colonize cranberry roots internally. The genomes of these fungi were sequenced, assembled and annotated. Genomic analyses focused on secreted proteins and biosynthetic gene clusters (BGCs). We found an extensive repertoire of carbohydrate-active enzymes and proteases that could assist in recycling organic nutrients, rendering them accessible to plants; these enzymes may also facilitate root colonization. In addition, effector proteins were predicted; these molecules may assist endophytes to escape the plant immune system and favour colonization. We inferred 139 biosynthetic gene clusters (BGCs) across the three examined fungi. Remarkably, the product of around 90% of BGCs are unknown. Finally, transcriptomic analyses were performed to determine how EC200, EC205 and EC208 respond to the presence of cranberry, simulated by the addition of cranberry extract in the culture medium. The two major conclusions of this work are that the roots of the sampled cranberry plants are dominated by endophytes with biocontrol abilities, and that EC200, EC205 and EC208 encode a broad repertoire of proteins that could be involved in plant-endophyte interactions.

Une réconciliation entre un arbre de gènes et un arbre d’espèces décrit une histoire d’évolution des gènes homologues en termes de duplications et pertes de gènes. Pour inférer une réconciliation pour un arbre de gènes et un arbre d’espèces, la parcimonie est généralement utilisée selon le nombre de duplications et/ou de pertes. Les modèles de réconciliation sont basés sur des critères probabilistes ou combinatoires. Le premier article définit un modèle combinatoire simple et général où les duplications et les pertes sont clairement identifiées et la réconciliation parcimonieuse n’est pas la seule considérée. Une architecture de toutes les réconciliations est définie et des algorithmes efficaces (soit de dénombrement, de génération aléatoire et d’exploration) sont développés pour étudier les propriétés combinatoires de l’espace de toutes les réconciliations ou seulement les plus parcimonieuses. Basée sur le processus classique nommé naissance-et-mort, un algorithme qui calcule la vraisemblance d’une réconciliation a récemment été proposé. Le deuxième article utilise cet algorithme avec les outils combinatoires décrits ci-haut pour calculer efficacement (soit approximativement ou exactement) les probabilités postérieures des réconciliations localisées dans le sous-espace considéré. Basé sur des taux réalistes (selon un modèle probabiliste) de duplication et de perte et sur des données réelles/simulées de familles de champignons, nos résultats suggèrent que la masse probabiliste de toute l’espace des réconciliations est principalement localisée autour des réconciliations parcimonieuses. Dans un contexte d’approximation de la probabilité d’une réconciliation, notre approche est une alternative intéressante face aux méthodes MCMC et peut être meilleure qu’une approche sophistiquée, efficace et exacte pour calculer la probabilité d’une réconciliation donnée. Le problème nommé Gene Tree Parsimony (GTP) est d’inférer un arbre d’espèces qui minimise le nombre de duplications et/ou de pertes pour un ensemble d’arbres de gènes. Basé sur une approche qui explore tout l’espace des arbres d’espèces pour les génomes considérés et un calcul efficace des coûts de réconciliation, le troisième article décrit un algorithme de Branch-and-Bound pour résoudre de façon exacte le problème GTP. Lorsque le nombre de taxa est trop grand, notre algorithme peut facilement considérer des relations prédéfinies entre ensembles de taxa. Nous avons testé notre algorithme sur des familles de gènes de 29 eucaryotes. / A reconciliation between a gene tree and a species tree depicts an evolutionary scenario of the homologous genes in terms of gene duplications and gene losses. To infer such a reconciliation given a gene tree and a species tree, parsimony is generally used according to the number of gene duplications and/or losses. The combinatorial models of reconciliation are based on probabilistic or combinatorial criteria. The first paper defines a simple and more general combinatorial model of reconciliation which clearly identifies duplication and loss events and does not only induce the most parsimonious reconciliation. An architecture of all possible reconciliations is developed together with efficient algorithms (that is counting, randomization, and exploration) to study combinatorial properties of the space of all reconciliations or only the most parsimonious ones. Based on the classical birth-death process, an algorithm that computes the likelihood of a reconciliation has recently been proposed. The second paper uses this algorithm together with the combinatorial tools described above to compute efficiently, either exactly or approximately, the posterior probability of the reconciliations located in the considered subspace. Based on realistic gene duplication and loss rates and on real/simulated datasets of fungal gene families, our results suggest that the probability mass of the whole space of reconciliations is mostly located around the most parsimonious ones. In the context of posterior probability approximation, our approach is a valuable alternative to a MCMC method and can competes against a sophisticated, efficient, and exact computation of the probability of a given reconciliation. The Gene Tree Parsimony (GTP) problem is to infer a species tree that minimizes the number of duplications and/or losses over a set of gene family trees. Based on a new approch that explores the whole species tree space for the considered taxa and an efficient computation of the reconciliation cost, the third paper describes a Branch-and- Bound algorithm that solves exactly the GTP problem. When the considered number of taxa is too large, our algorithm can naturally take into account predefined relationships between sets of taxa. We test our algorithm on a dataset of eukaryotic gene families spanning 29 taxa.

Le caryotype moléculaire permet d’identifier un CNV chez 10-14% des individus atteints de déficience intellectuelle et/ou de malformations congénitales. C’est pourquoi il s’agit maintenant de l’analyse de première intention chez ces patients. Toutefois, le rendement diagnostique n’est pas aussi bien défini en contexte prénatal et l’identification de CNVs de signification clinique incertaine y est particulièrement problématique à cause du risque d’interruption de grossesse. Nous avons donc testé 49 fœtus avec malformations majeures et un caryotype conventionnel normal avec une micropuce CGH pangénomique, et obtenu un diagnostic dans 8,2% des cas. Par ailleurs, des micropuces à très haute résolution combinant le caryotype moléculaire et le génotypage de SNPs ont récemment été introduites sur le marché. En plus d’identifier les CNVs, ces plateformes détectent les LOHs, qui peuvent indiquer la présence d’une mutation homozygote ou de disomie uniparentale. Ces anomalies pouvant être associées à la déficience intellectuelle ou à des malformations, leur détection est particulièrement intéressante pour les patients dont le phénotype reste inexpliqué. Cependant, le rendement diagnostique de ces plateformes n’est pas confirmé, et l’utilité clinique réelle des LOHs n’est toujours pas établie. Nous avons donc testé 21 enfants atteints de déficience intellectuelle pour qui les méthodes standards d’analyse génétique n’avaient pas résulté en un diagnostic, et avons pu faire passer le rendement diagnostique de 14,3% à 28,6% grâce à l’information fournie par les LOHs. Cette étude démontre l’utilité clinique d’une micropuce CGH pangénomique chez des fœtus avec malformations, de même que celle d’une micropuce SNP chez des enfants avec déficience intellectuelle. / Molecular karyotyping identifies a CNV in 10-14% of individuals affected with intellectual disability and/or congenital abnormalities. Therefore, it is now the first-tier analysis for these patients. However, the diagnostic yield is not as clear in the prenatal context, and the risk of pregnancy termination makes the detection of variants of uncertain clinical significance particularly problematic. We tested 49 fetuses with major malformations and a normal karyotype, using a pangenomic CGH array, and obtained a diagnosis in 8.2% of cases. Furthermore, high-resolution microarrays combining molecular karyotyping and SNP genotyping were recently introduced on the market. In addition to identifying CNVs, these platforms detect LOHs, which can indicate the presence of a homozygous mutation or of uniparental disomy. Since these abnormalities can be associated with intellectual disability or congenital abnormalities, their detection is of particular interest for patients whose phenotype remains unexplained. However, the diagnostic yield obtained with these platforms is not confirmed, and the real clinical value of LOH detection is not yet established. We tested 21 children affected with intellectual disability for whom standard genetic analyses failed to provide a diagnosis, and were able to increase the diagnostic yield from 14.3% to 28.6% as a result of the information provided by LOHs. This study shows the clinical usefulness of pangenomic CGH arrays in fetuses with malformation(s), as well as that of SNP arrays in children with intellectual disability.

Une réconciliation entre un arbre de gènes et un arbre d’espèces décrit une histoire d’évolution des gènes homologues en termes de duplications et pertes de gènes. Pour inférer une réconciliation pour un arbre de gènes et un arbre d’espèces, la parcimonie est généralement utilisée selon le nombre de duplications et/ou de pertes. Les modèles de réconciliation sont basés sur des critères probabilistes ou combinatoires. Le premier article définit un modèle combinatoire simple et général où les duplications et les pertes sont clairement identifiées et la réconciliation parcimonieuse n’est pas la seule considérée. Une architecture de toutes les réconciliations est définie et des algorithmes efficaces (soit de dénombrement, de génération aléatoire et d’exploration) sont développés pour étudier les propriétés combinatoires de l’espace de toutes les réconciliations ou seulement les plus parcimonieuses. Basée sur le processus classique nommé naissance-et-mort, un algorithme qui calcule la vraisemblance d’une réconciliation a récemment été proposé. Le deuxième article utilise cet algorithme avec les outils combinatoires décrits ci-haut pour calculer efficacement (soit approximativement ou exactement) les probabilités postérieures des réconciliations localisées dans le sous-espace considéré. Basé sur des taux réalistes (selon un modèle probabiliste) de duplication et de perte et sur des données réelles/simulées de familles de champignons, nos résultats suggèrent que la masse probabiliste de toute l’espace des réconciliations est principalement localisée autour des réconciliations parcimonieuses. Dans un contexte d’approximation de la probabilité d’une réconciliation, notre approche est une alternative intéressante face aux méthodes MCMC et peut être meilleure qu’une approche sophistiquée, efficace et exacte pour calculer la probabilité d’une réconciliation donnée. Le problème nommé Gene Tree Parsimony (GTP) est d’inférer un arbre d’espèces qui minimise le nombre de duplications et/ou de pertes pour un ensemble d’arbres de gènes. Basé sur une approche qui explore tout l’espace des arbres d’espèces pour les génomes considérés et un calcul efficace des coûts de réconciliation, le troisième article décrit un algorithme de Branch-and-Bound pour résoudre de façon exacte le problème GTP. Lorsque le nombre de taxa est trop grand, notre algorithme peut facilement considérer des relations prédéfinies entre ensembles de taxa. Nous avons testé notre algorithme sur des familles de gènes de 29 eucaryotes. / A reconciliation between a gene tree and a species tree depicts an evolutionary scenario of the homologous genes in terms of gene duplications and gene losses. To infer such a reconciliation given a gene tree and a species tree, parsimony is generally used according to the number of gene duplications and/or losses. The combinatorial models of reconciliation are based on probabilistic or combinatorial criteria. The first paper defines a simple and more general combinatorial model of reconciliation which clearly identifies duplication and loss events and does not only induce the most parsimonious reconciliation. An architecture of all possible reconciliations is developed together with efficient algorithms (that is counting, randomization, and exploration) to study combinatorial properties of the space of all reconciliations or only the most parsimonious ones. Based on the classical birth-death process, an algorithm that computes the likelihood of a reconciliation has recently been proposed. The second paper uses this algorithm together with the combinatorial tools described above to compute efficiently, either exactly or approximately, the posterior probability of the reconciliations located in the considered subspace. Based on realistic gene duplication and loss rates and on real/simulated datasets of fungal gene families, our results suggest that the probability mass of the whole space of reconciliations is mostly located around the most parsimonious ones. In the context of posterior probability approximation, our approach is a valuable alternative to a MCMC method and can competes against a sophisticated, efficient, and exact computation of the probability of a given reconciliation. The Gene Tree Parsimony (GTP) problem is to infer a species tree that minimizes the number of duplications and/or losses over a set of gene family trees. Based on a new approch that explores the whole species tree space for the considered taxa and an efficient computation of the reconciliation cost, the third paper describes a Branch-and- Bound algorithm that solves exactly the GTP problem. When the considered number of taxa is too large, our algorithm can naturally take into account predefined relationships between sets of taxa. We test our algorithm on a dataset of eukaryotic gene families spanning 29 taxa.

La génomique comparative est une discipline importante pour la compréhension de l'évolution du vivant. Différentes méthodes de comparaison existent, nous nous intéressons ici en particulier aux mesures de (dis)similarités entre les génomes. Dans cette étude, nous étudions 3 mesures : les nombres d'adjacences, de points de cassures et d'intervalles communs. En présence de gènes dupliqués ou lorsque l'ordre des gènes n'est que partiellement connu, calculer ces mesures est un problème connu pour être NP-difficile. D'une part, nous désirons calculer les nombres d'adjacences et de points de cassures pour trois modèles (exemplaire, intermédiaire, maximum) entre deux génomes possédant des duplications. Afin d'obtenir un algorithme exact, nous modélisons ces problèmes en programmes pseudo-booléens. Après expérimentation sur 12 génomes de γ-protéobactéries, nous obtenons suffisamment de résultats pour : comparer les deux mesures et les 3 modèles et évaluer des heuristiques. À ce titre, nous proposons une famille d'heuristiques basée sur une recherche de plus longue sous-séquence commune qui donne de très bons résultats sur ces données. Parallèlement à cela, nous avons étudié, pour différents problèmes de calcul de mesures entre deux génomes avec duplication, l'approximation polynomial. D'autre part, nous calculons les nombres d'adjacences et d'intervalles communs entre deux ordres partiels (avec la possibilité qu'un des ordres soit total). Nous utilisons de nouveau une approche de programmation pseudo-booléenne. À l'aide de près de 800 génomes simulés, nous étudions l'influence de paramètres inhérents aux ordres partiels et nous comparons les deux mesures étudiées.

La compréhension de la dynamique des réarrangements génomiques est importante en phylogénie. La phylogénie est l'étude de l'évolution des espèces. Un but majeur est d'établir les relations d'évolution au sein d'un groupe d'espèces, pour déterminer la topologie de l'arbre d'évolution formé par ce groupe et des ancêtres communs à certains sous-ensembles. Pour ce faire, il est naturellement très utile de disposer d'un moyen d'évaluer les distances évolutionnaires relatives entre des espèces, ou encore d'être capable d'inférer à un groupe d'espèces le génome d'un ancêtre commun à celles-ci. Ce travail de thèse, dans la lignée d'autres travaux, consiste à élaborer de tels moyens, ici dans des cas particuliers où les génomes possèdent des gènes en multiples copies, ce qui complique les choses. Plusieurs hypotèses explicatives de la présence de duplications ont été considérées, des formules de distance ainsi que des algorithmes de calcul de scénarios ont été élaborés, accompagnés de preuves de complexité.