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.

Les phénomènes évolutifs qui perturbent l'organisation des gènes dans les génomes eucaryotes sont de deux types : les changements dans l'ordre des gènes, ou réarrangements, et les modifications du contenu en gènes du génome, par duplications, délétions ou gains de gènes. Ces processus sont mal connus, tant au niveau de leurs mécanismes d'apparition que de leur impact fonctionnel et sélectif. Ce travail de thèse s'articule autour de deux projets. Le premier s'intéresse à la distribution des points de cassure de réarrangements évolutifs entre un génome ancestral et ses descendants modernes. Cette distribution a été modélisée en fonction des caractéristiques locales du génome pour mettre en évidence quels facteurs influencent la probabilité de cassure. Nos résultats montrent que la distribution des cassures peut s'expliquer simplement comme une fonction de la longueur des espaces intergéniques, fonction qui est cependant non-linéaire contrairement aux attentes sous un régime aléatoire classique. La répartition des points de cassure dans les génomes semble principalement liée à des propriétés de structure, et n'est que peu soumise à des contraintes de sélection. Elle pourrait être liée à la structure chromatinienne du génome. Le second projet s'inscrit dans le cadre du séquençage du génome du poisson zèbre, et fournit un aperçu global de l'organisation de ce génome. Les génomes de poissons téléostéens sont anciennement dupliqués : l'analyse est axée sur les conséquences de cette duplication. Les résultats montrent que le génome du poisson zèbre présente une organisation assez typique d'un génome téléostéen. Les gènes retenus en deux copies après la duplication du génome appartiennent à des catégories fonctionnelles particulières, et sont biaisés vers des gènes déjà conservés après les duplications 1R et 2R ayant eu lieu au début de l'histoire des vertébrés.

Les Spartines jouent un rôle écologique majeur sur les marais salés. Elles représentent un excellent modèle pour appréhender les conséquences écologiques de la spéciation par hybridation et polyploïdie dans le contexte d'invasion biologique. On s'intéresse plus particulièrement, à l'hybridation récente entre une espèce hexaploïde d'origine américaine Spartina alterniflora et une espèce hexaploïde européenne S. maritima ayant donnés deux hybrides F1 (S. x townsendii et S. x neyrautii) et la nouvelle espèce envahissante allododécaploïde (S. anglica). Les nouvelles technologies de séquençage haut-débit facilitent l'exploration de ces génomes peu connus. L'assemblage et l'annotation d'un transcriptome de référence ont permis d'annoter 16 753 gènes chez les spartines hexaploïdes et d'identifier des gènes d'intérêts écologique et évolutif. Une sélection de ces gènes a ensuite été analysée à travers une étude d'expression par PCR quantitative sur les populations naturelles des 5 espèces du complexe. Les résultats ont permis de mettre en évidence une expression homogène intra-populations mais une grande variabilité entre les espèces. L'analyse du génome des Spartines a ciblé prioritairement le développement de ressources génomiques concernant l'espèce S. maritima pour l'analyse des compartiments codant et répété à l'aide de séquençage d'une banque BAC et d'un run de pyroséquençage d'ADN génomique. Les analyses ont permis d'évaluer une proportion d'éléments répétés représentant près de 30% du génome. Les données générées ont alors été comparées avec les génomes séquencés phylogénétiquement proches et ont permis de premières comparaisons entre les spartines et les autres Poaceae.

La diversité d’une espèce est représentée par la somme de la diversité de chacun des individus qui la compose. Elle peut être observée à différentes échelles : individuelle, organique, tissulaire, cellulaire, génomique, génique, ou bien à l’échelle de la base nucléotidique. L’étude de la diversité d’une espèce est importante pour mieux la comprendre et nous permettre de retracer son histoire évolutive, de la comparer avec d’autres espèces notamment entre espèces sauvages et cultivées. Nous nous intéressons aux processus de domestication, et particulièrement à leurs impacts sur la structure du pan-génome. Le pan-génome est divisé en trois compartiments : (i) le core-génome qui contient tous les gènes présents chez tous les individus de l’espèce ; (ii) le génome dispensable qui contient l’ensemble des gènes qui sont absents chez au moins un individu ; (iii) et enfin le génome individu-spécifique qui contient les gènes présents uniquement chez un individu.L’objectif de ce travail de thèse était de mettre au point une nouvelle méthode d’analyse pan-génomique applicable sur un grand nombre d’individus. Pour cela, nous avons travaillé sur un jeu de données de reséquençage massif du riz Africain cultivé O. glaberrima et de son ancêtre sauvage O. barthii. Dans un premier temps nous avons vérifié l’existence d’une structure pan-génomique sur notre modèle. Pour cela nous avons travaillé à petite échelle avec trois accessions de l’espèce cultivée. Elles ont d’abord été séquencées, assemblées, annotées puis nous avons cherché à détecter des séquences spécifiques à chacune de ces accessions.Dans un second temps nous avons mis au point notre méthode en travaillant avec près de 200 génomes des deux espèces.Ces génomes ont été séquencés grâce aux technologies NGS puis directement mappés sur un génome de référence externe, celui du riz Asiatique. Nous avons alors appliqué notre méthode d’analyse pan-génomique basée sur la déviation de la profondeur deséquençage pour chaque gène. Nous avons ensuite comparé les enrichissement d’ontologies par compartiments et par espèce dans le but d’identifier des différences liées aux processus de domestication. Enfin, nous avons étudié plus précisément les appartenances pan-génomiques des membres de famille de gènes.Parce que le pan-génome de l’espèce cultivé est plus petit que le core-génome de l’espèce sauvage nous avons confirmé la perte de diversité en terme de présence/ absence de gènes chez le riz Africain au cours du processus de domestication. Curieusement nous avons aussi mis en avant l’augmentation du nombre de gènes dispensable chez l’espèce cultivée par rapport à son relatif sauvage.Ainsi, malgré une forte réduction du pan-génome de l’espèce cultivé lors de la « première » sélection, les 1000 générations de processus de domestication ont suffit à réintroduire une forme de diversité à travers l’augmentation du nombre de gènes dispensables.Afin d’automatiser une grande partie des manipulations d’analyses de données NGS nous avons aussi développé un outil de génération de pipelines d’analyses. De part sa généricité et sa robustesse il pourra être utilisé dans différents domaines, pour plu-sieurs types de données. Grâce aux nombreux logiciels qui y sont intégrés et de par le suivi que l’équipe de développement entend poursuivre, il pourra être utilisé dans la caractérisation de plus en plus de choses. Par exemple les variations structurales, les associations génotypes-phénotypes, l’épigénétique et pourquoi pas la métagénomique.Ce travail a permis la mise au point d’une nouvelle méthode d’analyse des données pan-génomiques rapide de par sa vision globale plutôt que via des comparaisons deux-à-deux. Cette méthode s’adresse aux génomes grands et complexes comme ceux des plantes, mais aussi aux jeux de données massifs. / Species diversity is represented by the sum of the diversity of each of the individuals composing it. It can be seen at differents cales: individual, organic, tissular, cellular, genomic, gene, and even nucleotic. The study of the diversity of species is important to better understand and allow tracking its evolutionary history, comparing it to other species, in particular wild to cultivated. We focused on the domestication, and particularly its impact on the pan-genome structure.The pan-genome is divided into three compartments: (i) the core-genome containing all the genes present in all individuals of the species; (ii) the dispensable genome containing all genes absent in at least one individual; (iii) and finally the individual-specific genome containing genes present only in one individual.The objective of this thesis was to develop a new method for pan-genomic analysis that can apply to a large number of indi-viduals. For this, we worked on a massive resequencing data set of cultivated African rice O. glaberrima and of its wild ancestor O. barthii. At first we checked the existence of a pan-genomic structure on our model. For this we worked on a small scale, with three accessions of cultivated species. They were sequenced, assembled, annotated then analyzed to detect specific sequences for each accession.Secondly we developed our approach working with nearly 200 genomes of both species. These genomes were sequenced using Illumina technology and mapped to the external reference genome, of the Asian rice. We applied our pan-genomic method analysis based on the deviation of the depth of sequencing for each gene. We then compared the ontology enrichment compartments and species in order to identify differences related to the domestication process. Finally, we looked specifically to pan-genomic genes belonging to gene family. Because the pan-genome of the cultivated species is smaller than the core-genome of the wild one, we confirmed the loss ofdiversity in terms of presence/ absence of genes in African rice during the domestication process. Curiously we have also high lighted the increase in the number of dispensable genes in the crop from its wild relative. Thus, despite a sharp reduction of the pan-genomeof the species cultivated in the “first” selection, the 1,000 generations of domestication process were enough to reintroduce a formof diversity through increasing the number of dispensable genes.To automate much of the data analysis of NGS manipulations we have also developed a tool to generate analysis pipelines.Due to its generic and robustness it can be used in different areas, for several types of data. With many softwares integrated and by monitoring that the development team will continue, it may be used in the characterization of more and more things. For example,structural variations, genotype-phenotype associations, epigenetics and metagenomics. This work enabled the development of a new analytical method for rapid genome-wide data through its global vision ratherthan through two by two comparisons. This method is for large and complex genomes such as those of plants, but also to massivedata sets.

Les picocyanobactéries marines des genres Prochlorococcus et Synechococcus sont les organismes photosynthétiques les plus abondants de la planète et ils contribuent de façon substantielle à la production primaire mondiale. Alors que le genre Prochlorococcus se caractérise par sa forte abondance dans les régions oligotrophes et son génome réduit, le genre Synechococcus se distingue par sa grande diversité génétique et pigmentaire ainsi qu'une aire de distribution plus étendue.Le principal objectif de ce travail a été de mettre en relation la diversité génétique de ces organismes avec leur niche écologique par des approches de génomique comparative et de métagénomique. Tout d'abord, le développement d'une méthode de scaffolding (WiseScaffolder) a permis de clore 32 nouveaux génomes de Synechococcus, lesquels ont été intégrés au système d'information Cyanorak, dédié à l'annotation de gènes orthologues. Ces nouveaux génomes, complétant les 65 génomes disponibles pour ces deux genres, ont fait l'objet d'analyses comparatives afin de mieux comprendre la diversité et l'évolution de ce phylum et de définir les gènes spécifiques de différents groupes phylogénétiques, potentiellement liés à leur adaptation à des niches écologiques distinctes.Ces génomes ont ensuite été utilisés comme référence, en conjonction avec le gène marqueur petB, pour analyser les données de métagénomique issues de l'expédition TARA-Océans. Ces analyses ont notamment mis en lumière la diversité génétique, la distribution et l'importance écologique de certains clades phylogénétiques. Ce travail soulève de nouvelles hypothèses quant au rôle des picocyanobactéries dans le fonctionnement global des océans. / Marine picocyanobacteria Prochlorococcus and Synechococcus genera are the most abundant photosynthetic organisms and contribute substantially to global primary production. While the genus Prochlorococcus is characterized by its high abundance in oligotrophic regions and its reduced genome, Synechococcus is characterized by a larger genetic and pigment diversity and a wider area of distribution.The main objective of this PhD thesis was to link the genetic diversity of these organisms to the environmental conditions of their ecological niche by comparative genomics and metagenomics approaches. Firstly, the development of a scaffolding method (WiseScaffolder) has allowed us to close 32 new genomes of Synechococcus which were integrated into the Cyanorak information system dedicated to the annotation of orthologous genes. These new genomes, supplementing the 65 genomes previously available for these two genera, allowed us to perform comparative analyses which led to a better understanding of the diversity and evolution of this phylum and to the definition of genes sets specific to different phylogenetic groups and thus potentially related to their adaptation to different ecological niches.These genomes were then used as reference, in conjunction with the marker gene petB gene, to analyze metagenomic data produced in the frame of the Tara-Oceans Expedition. In particular, these analyzes highlighted the genetic diversity, distribution and ecological importance of some phylogenetic clades. This work raises new hypotheses about the role of picocyanobacteria in the overall functioning of the oceans.

Cette thèse porte sur l'histoire évolutive des gènes de vertébrés. Deux types de phénomènes évolutifs peuvent perturber l’organisation des gènes dans les génomes eucaryotes : les modifications du contenu en gènes des génomes par duplications ou délétions de gènes, et les changements dans l’ordre des gènes par réarrangements. L’impact fonctionnel et sélectif de ces processus sur les génomes est encore mal connu.Ce travail de thèse s’articule autour de trois projets portant sur les événements de duplication et de délétion qui modifient le nombre de copies d'un gène. Nous nous sommes intéressés à ces événements à partir d’arbres phylogénétiques reconstruits à l’échelle de génomes entiers. Dans une première partie nous avons examiné le cas où ces événements seraient sous sélection négative, en étudiant les arbres de gènes ou aucune duplication ou délétion ne s'est fixée. Nous avons observé que ces gènes avaient des propriétés particulières et nous proposons des hypothèses pour les expliquer. Dans une deuxième partie nous nous sommes intéressés aux duplications de gènes et aux corrélations que l'on observe avec l'évolution des fonctions biologiques. Enfin en dernière partie nous avons étudié en détail la famille de gènes ROBO dont une des copies aurait acquis une fonction différente dans le développement du système nerveux des mammifères sous l’influence de la sélection positive. Dans leur ensemble ces résultats apportent de nouveaux éléments pour mesurer et comprendre l’impact global des contraintes ou des avantages que les duplications de gènes en particulier, et le changement du nombre de copies des gènes en général, peuvent exercer sur un génome de vertébré. / This thesis is about the evolutionary history of vertebrates genes. Two categories of evolutionary processes can disrupt the gene organization in eukaryotic genomes: changes in the content of genomes by gene duplications or gene deletions, and changes in the order of the genes by rearrangements. Functional and selective impacts of these processes on genomes are poorly understood.This thesis covers three different projects about duplication and deletion events that change the number of gene copies. We were interested in these events from phylogenetic trees reconstructed at the scale of whole genomes. In the first part we examined the case where these events would be under negative selection, by studying phylogenetic gene trees where no duplication or deletion was fixed. We found that these genes have special properties and propose hypotheses to explain them. In the second part we looked at gene duplications and correlated these events with the evolution of biological functions. Finally in the last part we have studied in detail the ROBO genes family in which one copy has acquired a different function in the developing nervous system of mammals under the influence of positive selection.Taken together these results provide new elements to measure and understand the global impact of constraints or advantages that gene duplications in particular, and the change of genes copy number in general, can have on a vertebrate genome.

Le travail décrit dans cette thèse a commencé avec la découverte d’effets anti-inflammatoires chez certaines souches de L. delbrueckii. Il avait été montré que l’effet anti-inflammatoire est souche-dépendant, et implique l’action de protéines exposées à la surface de la bactérie. Dans le but d’identifier l’effecteur bactérien à l’origine de l’effet immuno-modulateur, 8 souches de L. delbrueckii ont été sélectionnées. Deux de ces souches sont à fort effet anti-inflammatoires, et les 6 restantes sont à effet faible ou intermédiaire. Pour l’identification des protéines potentiellement responsables pour l’effet anti-inflammatoire, des études de génomique et transcriptomique comparatives des 8 souches de L.delbrueckii ont été entreprises, ainsi qu’une étude comparative du protéome de surface bactérienne.La première partie de cette thèse décrit les résultats de finition du génome d’une des deux souches hautement anti-inflammatoires. Cette étape a révélé que la partie manquante de la séquence génomique était principalement composée de séquences répétées de type séquences d’insertions (IS), dont le nombre s’avère particulièrement élevé.La deuxième partie de la thèse décrit une étape de valorisation des données génomiques à travers une étude comparative entre souches de la ssp. lactis et souches de la ssp. bulgaricus. Cette étude révèle que les deux ssp. de L. delbrueckii évoluent en adaptation au milieu lait. Toutefois, la ssp. bulgaricus semble avoir atteint un stade d’adaptation plus avancé que celui de la ssp. lactis. L’adaptation des deux ssp. à leur environnement se fait principalement par un phénomène de perte spontanée de gènes devenus superflus.Une étude plus avancée de la structure génomique des deux ssp. révèle deux nouveaux aspects des différences de structure génomique. Tout d’abord, au sein du core génome des deux sous-espèces, les évènements d’échange génétique et recombinaison ont contribué plus à la diversité au sein de la ssp. lactis qu’à la diversité chez la ssp. bulgaricus. Ensuite, une structure inversée répétée de grande taille, rarement observée dans les génomes bactériens, s’avère caractéristique de la ssp. bulgaricus. La troisième partie de thèse décrit les trois approches comparatives menées dans le but d’identifier les protéines bactériennes à l’origine de l’effet anti-inflammatoire. Au bout de ces études, nous avons sélectionné 56 gènes candidats, dont 41 ont été clonés dans un système d’expression hétérologue. Pour l’instant, 17 clones d’expression ont été testés in vitro pour leur potentiel immuno-modulateur. Les résultats préliminaires ont permis l’identification d’une protéine à effet anti-inflammatoire. / The work described in this thesis began with the discovery of anti -inflammatory effects in certain strains of L. delbrueckii. The anti- inflammatory effect had been shown to be strain - dependent, and implicate the action of bacterial surface exposed proteins.In order to identify the bacterial effector responsible for the immunomodulatory effect, eight strains of L. delbrueckii were selected. Two of these strains have a strong anti -inflammatory effect, whereas the remaining strains have a weak to intermediary effect. To identify proteins that may be responsible for the anti- inflammatory effect, comparative genomic and transcriptomic studies of the 8 L.delbrueckii strains were conducted, as well as a comparative study of the bacterial surface proteome.The first part of this thesis describes the genome finishing of one of the highly anti- inflammatory strains. This step revealed that the missing part of the genome sequence was mainly composed of repeated sequences such as insertions sequences (IS), that were present in a particularly high number.The second part of the thesis describes the valorisation of genomic data through a comparative study between ssp. lactis strains and ssp. bulgaricus strains. This study reveals that both L. delbrueckii ssp. are evolving in adaptation to the milk environment. However, the ssp. bulgaricus appears to have reached a more advanced stage of adaptation than the ssp. lactis. The adaptation of both ssp. to their environment is primarily a phenomenon of spontaneous loss of genes that have become superfluous. A more detailed study of the genome structure of the two ssp. reveals two important differences. Firstly, within the L. delbrueckii core genome, genetic exchange and recombination contributed much more to the ssp. lactis diversity than to the ssp. bulgaricus diversity. Furthermore, a large inverted repeat structure, rarely observed in bacterial genomes, appears to be characteristic of the ssp. bulgaricus.The third part of the thesis describes the three comparative approaches used to identify bacterial proteins responsible for the anti- inflammatory effect.We selected 56 candidate genes, of which 41 were cloned in a heterologous expression system. So far, 17 expression clones were tested in vitro for their immunomodulatory potential. The preliminary results allowed the identification of one protein with anti-inflammatory effects.

Le genre Rickettsia est composé de bactéries Gram-négatives, intracellulaires obligatoires qui causent un éventail de maladies humaines à travers le monde. Des nouvelles techniques ont permis de progresser dans l'identification et la classification des Rickettsia, y compris l'introduction de méthodes moléculaires comme la comparaison de séquences de gènes (ARNr 16S, ompA, ompB, gltA, sca4 …) et la création du statut de sous-espèce. La génomique et les techniques de séquençage de nouvelle génération ont permis d’accéder à une nouvelle façon d’en apprendre davantage sur la pathogenèse et l'évolution de Rickettsia. La première partie de cette thèse est une revue sur les avantages et les limites de la génomique en taxonomie des procaryotes, tandis que la seconde partie est constituée des analyses génomiques de cinq sous-espèces de Rickettsia et une nouvelle espèce de Rickettsia. En utilisant des méthodes de séquençage à haut débit, nous avons obtenu les génomes de R. sibirica sibirica, R. sibirica mongolitimonae, R. conorii indica, R. conorii caspia, R. conorii israelensis et R. gravesii. Ce travail constitue la base d’autres études qui permettront de mieux comprendre les mécanismes physiopathologiques, l’évolution, et la taxonomie des rickettsies. / The Rickettsia genus is composed of Gram-negative, obligate intracellular bacteria that cause a range of human diseases around the world. New techniques have led to progress in the identification and classification of Rickettsia, including the introduction of molecular methods like sequence comparison (16S rRNA, ompA, ompB, gltA, sca4 …) and the creation of the subspecies status. Genomics and next-generation sequencing have opened a new way to learn more about the pathogenesis and evolution of Rickettsia. The first part of this thesis is a review on the advantages and limitations of genomics in prokaryotic taxonomy, while the second part consists of the genomic analyses of five Rickettsia subspecies and a new Rickettsia species. Using high-throughput sequencing methods, we obtained the draft genomes of R. sibirica sibirica, R. sibirica mongolitimonae, R. conorii indica, R. conorii caspia, R. conorii israelensis, and R. gravesii. This work can be a basis of further studies to increase the understanding on the disease-causing mechanisms, evolutionary relationships, and taxonomy of rickettsiae.

Les souches microbiennes naturelles des fromages sont souvent caractérisées pour étudier leur contribution au développement des propriétés sensorielles (goût, odeur, texture) des fromages affinés. Une meilleure compréhension de ce rôle lors de l’affinage du fromage est essentielle afin de mieux contrôler la qualité de ceux-ci. Peu d’analyses génomiques en détails ont été effectuées sur les microorganismes de la microflore naturelle des fromages (microorganismes non inoculés), alors qu’un plus grand intérêt est porté sur les ferments inoculés. La caractérisation du génome complet de souches bactériennes provenant du terroir québécois permet d’en révéler le contenu en gènes et de prédire les voies métaboliques associées. Ceci permet également d’établir l’apport individuel de celles-ci à la production de composés aromatiques. Dans le cadre de ce travail, le génome complet de quatre souches Staphylococcus equorum ont été séquencés. Ensuite, une analyse détaillée du génome de ces quatre souches a été réalisée en effectuant l’assemblage et l’annotation fonctionnelle des ~2700 gènes prédits dans chacune des souches à l’étude. Des gènes impliqués potentiellement dans la protéolyse, la lipolyse et la dégradation du lactose, ont été retrouvés dans toutes les souches de S. equorum, révélant leur potentiel métabolique important dans le fromage. Plusieurs attributs intéressants des S. equorum ont également été identifiés par des analyses de génomique comparative. D’abord, la relation entre le regroupement phylogénétique des souches avec leurs sources d’isolement indique une possibilité d’adaptation des souches à leur niche écologique. La présence de gènes uniques ou peu partagés est aussi une caractéristique identifiable dans les génomes des souches étudiées et pouvant avoir un impact sur les métabolismes des souches. La caractérisation du génome de souches de S. equorum et les analyses phylogénomiques fournissent de nouvelles informations sur son rôle dans le fromage et des indices sur son potentiel métabolique. Les données génomiques obtenues permettront, lors de validations futures, de sélectionner des souches ayant des propriétés désirables en fonction des variétés fromagères afin d’obtenir des fromages de qualité optimale. / The natural microbiota of cheese has often been characterized to study their potential participation in the development of sensorial properties (taste, odour, texture) of the ripened cheeses. A better understanding of their role during cheese ripening is therefore essential in order to have a better control of its quality. Few in-depth genomic analyzes have been carried out on microorganisms of the natural microflora of cheese (non-inoculated microorganisms), while there is a greater interest for inoculated ferments. The genes possessed by bacterial strains of the Quebec terroir can be revealed by the characterization of their complete genome, leading to the prediction of the associated metabolic pathways. This also allows the establishment of the individual contribution of each strain to the production of aromatic compounds. As part of this work, the complete genome of four strains of Staphylococcus equorum were sequenced. Then, a detailed analysis of the genome of these four strains was completed by their assembly and the functional annotation of the ~ 2700 genes predicted in each of the studied strains. Genes potentially implicated in proteolysis, lipolysis and lactose degradation, were found in all S. equorum strains, revealing their potential metabolisms important for cheese. Several interesting attributes of S. equorum were also identified by comparative genomic analyses. First, the relation in between the phylogenetic grouping and the source of isolation of the strains, indicates a possible adaptation of the strains to their ecological niche. The presence of unique or barely shared genes is also a distinguishable characteristic of the studied strains and can have an impact on the metabolisms of the strains. The characterization of the genome of S. equorum strains and the phylogenomic analyzes have provided new information on their role in cheese and clues about their metabolic potential. The genomic data collected will allow during future validations the selection of strains with desirable properties in function of cheese variety to yield cheeses of optimal quality.

Pour mieux saisir les liens complexes entre génotype et phénotype, une méthode utilisée consiste à étudier les relations entre différents éléments biologiques (entre les protéines, entre les métabolites...). Celles-ci forment ce qui est appelé un réseau biologique, que l'on représente algorithmiquement par un graphe. Nous nous intéressons principalement dans cette thèse au problème de la recherche d'un motif (multi-ensemble de couleurs) dans un graphe coloré, représentant un réseau biologique. De tels motifs correspondent généralement à un ensemble d'éléments conservés au cours de l'évolution et participant à une même fonction biologique. Nous continuons l'étude algorithmique de ce problème et de ses variantes (qui admettent plus de souplesse biologique), en distinguant les instances difficiles algorithmiquement et en étudiant différentes possibilités pour contourner cette difficulté (complexité paramétrée, réduction d'instance, approximation...). Nous proposons également un greffon intégré au logiciel Cytoscape pour résoudre efficacement ce problème, que nous testons sur des données réelles.Nous nous intéressons également à différents problèmes de génomique comparative. La démarche scientifique adoptée reste la même: depuis une formalisation d'un problème biologique, déterminer ses instances difficiles algorithmiquement et proposer des solutions pour contourner cette difficulté (ou prouver que de telles solutions sont impossibles à trouver sous des hypothèses fortes) / To investigate the complex links between genotype and phenotype, one can study the relations between different biological entities. It forms a biological network, represented by a graph. In this thesis, we are interested in the occurrence of a motif (a multi-set of colors) in a vertex-colored graph, representing a biological network. Such motifs usually correspond to a set of elements realizing a same function, and which may have been evolutionarily preserved. We follow the algorithmic study of this problem, by establishing hard instances and studying possibilities to cope with the hardness (parameterized complexity, preprocessing, approximation...). We also develop a plugin for Cytoscape, in order to solve efficiently this problem and to test it on real data.We are also interested in different problems related to comparative genomics. The scientific method is the same: studying problems arising from biology, specifying the hard instances and giving solutions to cope with the hardness (or proving such solutions are unlikely)