[Français] Une fraction importante des génomes eucaryotes est constituée de Gènes Répétés en Tandem (GRT). Un mécanisme fondamental dans l’évolution des GRT est la recombinaison inégale durant la méiose, entrainant la duplication locale (en tandem) de segments chromosomiques contenant un ou plusieurs gènes adjacents. Différents algorithmes ont été proposés pour inférer une histoire de duplication en tandem pour un cluster de GRT. Cependant, leur utilisation est limitée dans la pratique, car ils ne tiennent pas compte d’autres événements évolutifs pourtant fréquents, comme les inversions, les duplications inversées et les délétions. Cette thèse propose différentes approches algorithmiques permettant d’intégrer ces événements dans le modèle de duplication en tandem classique. Nos contributions sont les suivantes: • Intégrer les inversions dans un modèle de duplication en tandem simple (duplication d’un gène à la fois) et proposer un algorithme exact permettant de calculer le nombre minimal d’inversions s’étant produites dans l’évolution d’un cluster de GRT. • Généraliser ce modèle pour l’étude d’un ensemble de clusters orthologues dans plusieurs espèces. • Proposer un algorithme permettant d’inférer l’histoire évolutive d’un cluster de GRT en tenant compte des duplications en tandem, duplications inversées, inversions et délétions de segments chromosomiques contenant un ou plusieurs gènes adjacents. / [English] Tandemly arrayed genes (TAGs) represent an important fraction of most genomes. A fundamental mechanism at the origin of TAG clusters is unequal crossing-over during meiosis, leading to the duplication of chromosomal segments containing one or many adjacent genes. Such duplications are called tandem duplications, as the duplicated segment is placed next to the original one on the chromosome. Different algorithms have been proposed to infer the tandem duplication history of a TAG cluster. However, their applicability is limited in practice since they do not take into account other frequent evolutionary events such as inversion, inverted duplication and deletion. In this thesis, we propose different algorithmic approaches allowing to integrate these evolutionary events in the original tandem duplication model of evolution. Our contributions are summarized as follows: • We integrate inversion events in a tandem duplication model restricted to single gene duplications, and we propose an exact algorithm allowing to compute the minimum number of inversions explaining the evolution of a TAG cluster. • We generalize this model to the study of orthologous TAG clusters in different species. • We propose an algorithm allowing to infer the evolutionary history of a TAG cluster through tandem duplication, inverted duplication, inversion and deletion of chromosomal segments containing one or many adjacent genes.

Les séquences protéiques naturelles sont le résultat net de l’interaction entre les mécanismes de mutation, de sélection naturelle et de dérive stochastique au cours des temps évolutifs. Les modèles probabilistes d’évolution moléculaire qui tiennent compte de ces différents facteurs ont été substantiellement améliorés au cours des dernières années. En particulier, ont été proposés des modèles incorporant explicitement la structure des protéines et les interdépendances entre sites, ainsi que les outils statistiques pour évaluer la performance de ces modèles. Toutefois, en dépit des avancées significatives dans cette direction, seules des représentations très simplifiées de la structure protéique ont été utilisées jusqu’à présent. Dans ce contexte, le sujet général de cette thèse est la modélisation de la structure tridimensionnelle des protéines, en tenant compte des limitations pratiques imposées par l’utilisation de méthodes phylogénétiques très gourmandes en temps de calcul. Dans un premier temps, une méthode statistique générale est présentée, visant à optimiser les paramètres d’un potentiel statistique (qui est une pseudo-énergie mesurant la compatibilité séquence-structure). La forme fonctionnelle du potentiel est par la suite raffinée, en augmentant le niveau de détails dans la description structurale sans alourdir les coûts computationnels. Plusieurs éléments structuraux sont explorés : interactions entre pairs de résidus, accessibilité au solvant, conformation de la chaîne principale et flexibilité. Les potentiels sont ensuite inclus dans un modèle d’évolution et leur performance est évaluée en termes d’ajustement statistique à des données réelles, et contrastée avec des modèles d’évolution standards. Finalement, le nouveau modèle structurellement contraint ainsi obtenu est utilisé pour mieux comprendre les relations entre niveau d’expression des gènes et sélection et conservation de leur séquence protéique. / Protein sequences are the net result of the interplay of mutation, natural selection and stochastic variation. Probabilistic models of molecular evolution accounting for these processes have been substantially improved over the last years. In particular, models that explicitly incorporate protein structure and site interdependencies have recently been developed, as well as statistical tools for assessing their performance. Despite major advances in this direction, only simple representations of protein structure have been used so far. In this context, the main theme of this dissertation has been the modeling of three-dimensional protein structure for evolutionary studies, taking into account the limitations imposed by computationally demanding phylogenetic methods. First, a general statistical framework for optimizing the parameters of a statistical potential (an energy-like scoring system for sequence-structure compatibility) is presented. The functional form of the potential is then refined, increasing the detail of structural description without inflating computational costs. Always at the residue-level, several structural elements are investigated: pairwise distance interactions, solvent accessibility, backbone conformation and flexibility of the residues. The potentials are then included into an evolutionary model and their performance is assessed in terms of model fit, compared to standard evolutionary models. Finally, this new structurally constrained phylogenetic model is used to better understand the selective forces behind the differences in conservation found in genes of very different expression levels.

L’immunité adaptive et la discrimination entre le soi et le non-soi chez les vertébrés à mâchoire reposent sur la présentation de peptides par les récepteurs d’histocompatibilité majeur de classe I. Les peptides antigéniques, présentés par les molécules du complexe d’histocompatibilité (CMH), sont scrutés par les lymphocytes T CD8 pour une réponse immunitaire appropriée. Le répertoire des peptides du CMH de classe I, aussi appelé immunopeptidome, est généré par la dégradation protéosomale des protéines endogènes, et a un rôle essentiel dans la régulation de l’immunité cellulaire. La composition de l’immunopeptidome dépend du type de cellule et peut présenter des caractéristiques liées à des maladies comme le cancer. Les peptides antigéniques peuvent être utilisés à des fins immunothérapeutiques notamment dans le traitement voire la prévention de certains cancers. La spectrométrie de masse est un outil de choix pour l’identification, le séquençage et la caractérisation de ces peptides. Cependant, la composition en acides aminés, la faible abondance et la diversité de ces peptides compliquent leur détection et leur séquençage. Nous avons développé un programme appelé StatPeaks qui permet de calculer un certains nombres de statistiques relatives à la fragmentation des peptides. À l’aide de ce programme, nous montrons sans équivoque que les peptides du CMH classe I, en mode de fragmentation par dissociation induite par collision (CID), fragmentent très différemment des peptides trypsiques communément utilisés en protéomique. Néanmoins, la fragmentation par décomposition induite par collision à plus haute énergie (HCD) proposée par le spectromètre LTQ-Orbitrap Velos améliore la fragmentation et fournit une haute résolution qui permet d’obtenir une meilleure confiance dans l’identification des peptides du CMH de classe I. Cet avantage permet d’effectuer le séquençage de novo pour identifier les variants polymorphes qui ne sont normalement pas identifiés par les recherches utilisant des bases de données. La comparaison des programmes de séquençage Lutefisk, pepNovo, pNovo, Vonode et Peaks met en évidence que le dernier permet d’identifier un plus grand nombre de peptides du CMH de classe I. Ce programme est intégré dans une chaîne de traitement de recherche d’antigènes mineurs d’histocompatibilité. Enfin, une base de données contenant les informations spectrales de plusieurs centaines de peptides du CMH de classe I accessible par Internet a été développée. / Adaptive immunity and discrimination between self and nonself in jawed vertebrates relies on the presentation of peptides by the major histocompatibility (MHC) class I receptors. Foreign or self peptide antigens presented by the MHC molecules are probed by CD8 T-cell lymphocyte for proper immune response. The repertoire of MHC I peptides collectively referred to as the immunopeptidome is generated through the proteasomal degradation of endogenous proteins and plays an important role in the regulation of cellular immunity. The composition of the immunopeptidome is cell specific and can harbor important hallmark of human diseases including cancer. Antigenic peptides can also be used in immunotherapy to mount an appropriate immune response against cancer cells displaying these peptides. Mass spectrometry is a tool of choice for the identification, sequencing and characterization of these peptides. However, the amino acid composition, the low abundance and diversity of these peptides make their detection and sequencing more challenging. We developed a software, called StatPeaks, that calculates statistics relative to the fragmentation of peptides. Using this software, we demonstrate that under collision induced dissociation (CID) MHC class I peptides fragment in a very different fashion than tryptic peptides, commonly used in proteomics. However, the higher-energy collisional dissociation (HCD) mode available on the LTQ-Orbitrap Velos enhances peptide fragmentation and provides high resolution fragment information that significantly improves the confidence in MHC class I peptide identification. This inherent advantage confers the ability to perform de novo sequencing to identify polymorphic variants that would normally elude conventional database searches. The comparison of de novo peptide sequencing software Lutefisk, pepNovo, pNovo, Vonode and Peaks indicated that the later software enabled higher rates of correct identification for MHC class I peptides. This software was integrated into a data analysis pipeline for the identification minor histocompatibility antigens (MiHAs). A web-based library that stores spectral information of hundreds of synthetic MHC class I peptides was developed in support to the needs of the immunopeptidome discovery program.

Les résultats ont été obtenus avec le logiciel "Insight-2" de Accelris (San Diego, CA) / En 2000, les structures à hautes résolutions des deux sous-unités ribosomiques ont finalement été mises à la disposition du public. L'année suivante, la structure aux rayons X de l'ensemble du ribosome bactérien a été publiée. Ces grandes réalisations ont ouvert une nouvelle ère dans l'étude des mécanismes de la synthèse des protéines. Dès lors, il est devenu possible de relier différents aspects de la fonction du ribosome à des éléments particuliers de sa structure tertiaire. L'établissement de la relation structure-fonction peut toutefois être problématique en raison de l'immense complexité de la structure du ribosome. En d'autres termes, pour que les données cristallographiques sur la structure tertiaire du ribosome soient vraiment utiles à la compréhension du fonctionnement du ribosome, ces données devraient elles-mêmes faire l'objet d'une analyse approfondie. Le travail, présenté ici, peut être vu comme une tentative de ce genre. En appliquant l’analyse systématique des structure cristallographiques du ribosome disponibles, nous avons essayé de résoudre deux problèmes fondamentaux de la biologie ribosomale concernant (1) la nature des réarrangements du ribosome qui ont lieu à différentes étapes de son cycle de fonctionnement et (2) la possibilité de reconstitution de l'évolution du ribosome du monde-à-ARN jusqu’à nos jours. Dans le premier projet, nous avons systématiquement comparé les structures du ribosome disponibles et de sa sous-unité afin d'identifier les domaines rigides, qui ont toujours la même conformation, et les régions flexibles dont la conformation peut varier d'une structure de ribosome à une autre. Il y a deux types de réarrangements structuraux connus dont nous voulions comprendre les mécanismes: le « ratchet-like movement » et la «fermeture de domaines ». Le premier a lieu au cours de la translocation du ribosome et est plus ou moins perçu comme une rotation d'une sous-unité par rapport à l'autre. Le deuxième se produit dans la petite sous-unité et est associé à la reconnaissance codon-anticodon au site A. La comparaison des conformations ribosomales disponibles a révélé les mécanismes spécifiques des deux réarrangements. Bien que la sélection de l'aminoacyl-ARNt appropriée au site A et la translocation du ribosome n'ont jamais été considérés comme ayant quelque chose en commun, nous démontrons ici que les réarrangements de la structure des ribosomes associés au premier processus répète les réarrangements associés au deuxième mais dans l’ordre inverse. En d'autres termes, pendant le cycle d'élongation, la fermeture de domaine et le « ratchet » peuvent ii être considérés comme un mouvement de va-et-vient, qui renvoie finalement le ribosome à sa conformation initiale. Dans le second projet, nous avons fait une tentative de reconstitution de l'évolution de l'ARNr 23S, du monde-à-ARN jusqu`à nos jours. Ici nous nous sommes basés sur la supposition que l'évolution de cette molécule a procédé par des insertions aléatoires des régions relativement courtes dans différentes parties de la chaîne poly-nucléotidique. Pour cela, nous avons élaboré des critères de l'intégrité de la structure ribosomale et présumé que lors de l'évolution, la structure du ribosome s’est toujours adaptée à ces standards. Nous avons examiné l'interaction de type A-mineur, un arrangement fréquent dans la structure de l’ARN ribosomique, constitué d'un empilement d’adénosines non-appariées, attachées à une double hélice. Nous avons supposé que dans toutes les interactions A-mineurs existantes dans le ribosome, la double hélice est apparue avant ou au moins simultanément avec la pile d’adénosines correspondantes. L'application systématique de ce principe à la structure tertiaire de l’ARN 23S a permis d'élucider de manière progressive l'ordre dans lequel les parties différentes de l’ARN 23S ont rejoint la structure. Pris ensemble, les deux projets démontrent l'efficacité de l'analyse systématique in-silico de la structure tertiaire du ribosome et ouvrent la voie à de futures découvertes. / In the year 2000, the first high-resolution structures of the individual ribosomal subunits became available to the public. The following year, the X-ray structure of the complete bacterial ribosome was published. These major achievements opened a new era in studying the mechanisms of protein synthesis. From then on, it became possible to attribute different aspects of the ribosome function to particular elements of its tertiary structure. However, establishing the structure-function relationships is problematic due to the immense complexity of the ribosome structure. In other words, in order to make the crystallographic data on the ribosome tertiary structure really useful for understanding of how the ribosome functions, it must be thoroughly analyzed. Here, based on systematic analysis of the available X-ray conformations of the ribosome we have tried to resolve two fundamental problems of the ribosome biology: concerning (1) the nature of rearrangements in the ribosome that take place at different steps of its functional cycle, and (2) the reconstruction of the ribosome evolution from the RNA world to present time. In the first project, we systematically compared the available structures of the ribosome and its subunits to identify rigid domains, which always have the same conformation, and flexible regions, where the conformation can vary from one ribosome structure to another. There were two known types of structural rearrangements whose mechanisms we wanted to understand: the ratchet-like motion and the so-called domain closure. The ratchet-like motion takes place during the ribosomal translocation and is roughly seen as a rotation of one subunit with respect to the other. The domain closure occurs in the small subunit and is associated with the cognate codon-anticodon recognition in the A-site. Comparison of the available ribosome conformations revealed the detailed mechanisms of both rearrangements. Although the selection of the cognate amino-acyl-tRNA in the A-site and of the ribosomal translocation have never been thought to have anything in common, we demonstrate that the rearrangements in the ribosome structure associated with the first process repeat in reverse order the rearrangements associated with the second process. In other words, during the ribosome elongation cycle, the domain closure and the ratchet-like motion can be seen as a back-and-forth movement, which eventually returns the ribosome to the initial conformation. iv In the second project, we attempted to reconstruct the evolution of the 23S rRNA from the RNA world to present time based on the presumption that the evolutionary expansion of this molecule proceeded though random insertions of relatively short regions into different regions of the polynucleotide chain. We developed criteria for integrity of the ribosome structure and presumed that during the evolutionary expansion, the ribosome structure always matched to these standards. For this, we specifically considered the A-minor interaction, a frequent arrangement in the rRNA structure consisting of a stack of unpaired adenosines tightly attached to a double helix. We presumed that in all A-minor interactions present in the ribosome, the double helix emerged before or at least simultaneously with the corresponding adenosine stack. The systematic application of this principle to the known tertiary structure of the 23S rRNA allowed us to elucidate in a step-vise manner the order in which different part of the modern 23S rRNA joined the structure. Taken together, the two projects demonstrate the effectiveness of the systematic in-silico analysis of the ribosome tertiary structure and pave the way for future discoveries.

Les interactions entre les squelettes sucre-phosphate de nucléotides jouent un rôle important dans la stabilisation des structures tertiaires de larges molécules d’ARN. Elles sont régies par des règles particulières qui gouverne leur formation mais qui jusque là demeure quasiment inconnues. Un élément structural d’ARN pour lequel les interactions sucre-phosphate sont importantes est le motif d’empaquetage de deux doubles hélices d’ARN le long du sillon mineur. Ce motif se trouve à divers endroits dans la structure du ribosome. Il consiste en deux doubles hélices interagissant de manière à ce que le squelette sucre-phosphate de l’une se niche dans le sillon mineur de l’autre et vice versa. La surface de contact entre les deux hélices est majoritairement formée par les riboses et implique au total douze nucléotides. La présente thèse a pour but d’analyser la structure interne de ce motif et sa dépendance de stabilité résultant de l’association optimale ou non des hélices, selon leurs séquences nucléotidiques. Il est démontré dans cette thèse qu’un positionnement approprié des riboses leur permet de former des contacts inter-hélices, par l’entremise d’un choix particulier de l’identité des pairs de bases impliquées. Pour différentes pairs de bases participant à ce contact inter-hélices, l’identité optimale peut être du type Watson-Crick, GC/CG, or certaines pairs de bases non Watson-Crick. Le choix adéquat de paires de bases fournit une interaction inter-hélice stable. Dans quelques cas du motif, l’identité de certaines paires de bases ne correspond pas à la structure la plus stable, ce qui pourrait refléter le fait que ces motifs devraient avoir une liberté de formation et de déformation lors du fonctionnement du ribosome. / Although backbone-backbone interactions play an important role in stabilization of the tertiary structure of large RNA molecules, the particular rules that govern the formation of these interactions remain basically unknown. One RNA structural element for which the backbone-backbone interactions are essential is the along-groove packing motif. This motif is found in numerous locations in the ribosome structure; it consists of two double helices arranged such that the backbone of one helix is packed in the minor groove of the other helix and vice versa. The contact area between the two helices is mostly formed by riboses and totally involves twelve nucleotides. Here we analyze the internal structure of the along-groove packing motif and the dependence of stability of the association of the helices on their nucleotide sequences. We show that the proper positioning of the riboses that allows them to form inter-helix contacts is achieved through the particular choice of the identities of the base pairs involved. For different base pairs participating in the inter-helix contacts the optimal identities can be Watson-Crick, GC/CG, or certain non-Watson-Crick base pairs. The proper choice of the base pairs provides for the stable inter-helix interaction. In some cases of the motif, the identities of certain base pairs do not correspond to the most stable structure, which may reflect the fact that these motifs should break and form during the ribosome function.

Les facteurs de transcription sont des protéines spécialisées qui jouent un rôle important dans différents processus biologiques tel que la différenciation, le cycle cellulaire et la tumorigenèse. Ils régulent la transcription des gènes en se fixant sur des séquences d’ADN spécifiques (éléments cis-régulateurs). L’identification de ces éléments est une étape cruciale dans la compréhension des réseaux de régulation des gènes. Avec l’avènement des technologies de séquençage à haut débit, l’identification de tout les éléments fonctionnels dans les génomes, incluant gènes et éléments cis-régulateurs a connu une avancée considérable. Alors qu’on est arrivé à estimer le nombre de gènes chez différentes espèces, l’information sur les éléments qui contrôlent et orchestrent la régulation de ces gènes est encore mal définie. Grace aux techniques de ChIP-chip et de ChIP-séquençage il est possible d’identifier toutes les régions du génome qui sont liées par un facteur de transcription d’intérêt. Plusieurs approches computationnelles ont été développées pour prédire les sites fixés par les facteurs de transcription. Ces approches sont classées en deux catégories principales: les algorithmes énumératifs et probabilistes. Toutefois, plusieurs études ont montré que ces approches génèrent des taux élevés de faux négatifs et de faux positifs ce qui rend difficile l’interprétation des résultats et par conséquent leur validation expérimentale. Dans cette thèse, nous avons ciblé deux objectifs. Le premier objectif a été de développer une nouvelle approche pour la découverte des sites de fixation des facteurs de transcription à l’ADN (SAMD-ChIP) adaptée aux données de ChIP-chip et de ChIP-séquençage. Notre approche implémente un algorithme hybride qui combine les deux stratégies énumérative et probabiliste, afin d’exploiter les performances de chacune d’entre elles. Notre approche a montré ses performances, comparée aux outils de découvertes de motifs existants sur des jeux de données simulées et des jeux de données de ChIP-chip et de ChIP-séquençage. SAMD-ChIP présente aussi l’avantage d’exploiter les propriétés de distributions des sites liés par les facteurs de transcription autour du centre des régions liées afin de limiter la prédiction aux motifs qui sont enrichis dans une fenêtre de longueur fixe autour du centre de ces régions. Les facteurs de transcription agissent rarement seuls. Ils forment souvent des complexes pour interagir avec l’ADN pour réguler leurs gènes cibles. Ces interactions impliquent des facteurs de transcription dont les sites de fixation à l’ADN sont localisés proches les uns des autres ou bien médier par des boucles de chromatine. Notre deuxième objectif a été d’exploiter la proximité spatiale des sites liés par les facteurs de transcription dans les régions de ChIP-chip et de ChIP-séquençage pour développer une approche pour la prédiction des motifs composites (motifs composés par deux sites et séparés par un espacement de taille fixe). Nous avons testé ce module pour prédire la co-localisation entre les deux demi-sites ERE qui forment le site ERE, lié par le récepteur des œstrogènes ERα. Ce module a été incorporé à notre outil de découverte de motifs SAMD-ChIP. / Transcription factors (TF) play important roles in various biological processes such as differentiation, cell cycle progression and tumorigenesis. They regulate gene expression by binding to specific DNA sequences (TFBS). Identifying these cis-regulatory elements is a crucial step to understand gene regulatory networks. Technological developments have enhanced DNA sequencing at genomic scale. On the basis of the resulting sequences, computational biologists now attempt to localize the most important functional regions, starting with genes, but also importantly the whole genome characterization of transcription factor binding sites and allow the development of several computational DNA motif discovery tools. Although these various tools are widely used and have been successful at discovering novel motifs, they are not adapted to ChIP-chip and ChIP-sequencing data. The main drawback of these approaches is that most of the predicted motifs represent artifacts due to an inefficient assessment of their enrichment. This thesis is about transcription factor proteins and statistical analysis of their binding sites in ChIP-chip and ChIP-sequencing data. The first objective was to develop a new do novo DNA motif discovery tool adapted to ChIP-chip and ChIP-sequencing data. SAMD-ChIP combines enumerative and stochastic strategies to predict enriched motifs in the vicinity of the ChIP peak summits. Our approach is an automated pipeline that includes motif discovery, motif clustering, motif optimization and finally motif identification using transcription factor (TF) databases. SAMD-ChIP outperforms state-of-the-art motif discovery tools in term of the number of predicted motifs and the prediction of rare and degenerate motifs. In particular, SAMD-ChIP efficiently identifies gapped motifs such as inverted or direct repeats bound by nuclear receptors and composite motifs resulting from the association of different single TF binding sites. The underlying assumption of the second objective is that in regulatory regions, binding sites of interacting transcription factors co-occur more often than expected by chance in the vicinity of the ChIP-peak summits. We proposed an approach to predict transcription factor binding sites co-localization based on the prediction of single motifs by do novo motif discovery tools or by using TFBS models from TF data bases.

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.

L’anémie falciforme est une maladie monogénique causée par une mutation dans le locus de la β-globine. Malgré le fait que l’anémie falciforme soit une maladie monogénique, cette maladie présente une grande hétérogénéité clinique. On présume que des facteurs environnementaux et génétiques contribuent à cette hétérogénéité. Il a été observé qu’un haut taux d’hémoglobine fœtale (HbF) diminuait la sévérité et la mortalité des patients atteints de l’anémie falciforme. Le but de mon projet était d’identifier des variations génétiques modifiant la sévérité clinique de l’anémie falciforme. Dans un premier temps, nous avons effectué la cartographie-fine de trois régions précédemment associées avec le taux d’hémoglobine fœtale. Nous avons ensuite effectué des études d’association pan-génomiques avec deux complications cliniques de l’anémie falciforme ainsi qu’avec le taux d’hémoglobine fœtale. Hormis les régions déjà identifiées comme étant associées au taux d’hémoglobine fœtale, aucun locus n’a atteint le niveau significatif de la puce de génotypage. Pour identifier des groupes de gènes modérément associés au taux d’hémoglobine fœtale qui seraient impliqués dans de mêmes voies biologiques, nous avons effectué une étude des processus biologiques. Finalement, nous avons effectué l’analyse de 19 exomes de patients Jamaïcains ayant des complications cliniques mineures de l’anémie falciforme. Compte tenu de la taille des cohortes de réplication disponibles, nous n’avons pas les moyens de valider statistiquement les variations identifiées par notre étude. Cependant, nos résultats fournissent de bons gènes candidats pour des études fonctionnelles et pour les réplications futures. Nos résultats suggèrent aussi que le β-hydroxybutyrate en concentration endogène pourraient influencer le taux d’hémoglobine fœtale. De plus, nous montrons que la cartographie-fine des régions associées par des études pan-génomiques peut identifier des signaux d’association additionnels et augmenter la variation héritable expliquée par cette région. / Sickle cell disease is a monogenic disease caused by a mutation in the β-globin locus. Although it is a monogenic disease, it shows a high clinical heterogeneity. Environmental and genetic factors are thought to play a role in this heterogeneity. It has been observed that a high fetal hemoglobin (HbF) levels correlates with a diminution of the severity and mortality of patients with sickle cell disease. The goal of my project was to identify genetic modifiers of the clinical severity of sickle cell disease. First, I performed the fine-mapping of three regions previously associated with HbF levels. Second, I performed genome-wide association studies with two clinical complications of sickle cell disease as well as with HbF levels. Since no new loci reached array-wide significance for HbF levels, I performed a pathway analysis to identify additional HbF loci of smaller effect size that might implicate shared biological processes. Finally, I performed the analysis of 19 whole exomes from Jamaican sickle cell disease patients with very mild complications. In conclusion, given the sample size of the replication cohorts available, we do not currently have the means to statistically validate the association signals. However, these results provide good candidate genes for functional studies and for future replication. Our results also suggest that β-hydroxybutyrate in endogenous levels could influence HbF levels. Furthermore, we show that fine-mapping the loci associated in genome-wide association studies can identify additional signals and increase the explained heritable variation.

Des évidences expérimentales récentes indiquent que les ARN changent de structures au fil du temps, parfois très rapidement, et que ces changements sont nécessaires à leurs activités biochimiques. La structure de ces ARN est donc dynamique. Ces mêmes évidences notent également que les structures clés impliquées sont prédites par le logiciel de prédiction de structure secondaire MC-Fold. En comparant les prédictions de structures du logiciel MC-Fold, nous avons constaté un lien clair entre les structures presque optimales (en termes de stabilité prédites par ce logiciel) et les variations d’activités biochimiques conséquentes à des changements ponctuels dans la séquence. Nous avons comparé les séquences d’ARN du point de vue de leurs structures dynamiques afin d’investiguer la similarité de leurs fonctions biologiques. Ceci a nécessité une accélération notable du logiciel MC-Fold. L’approche algorithmique est décrite au chapitre 1. Au chapitre 2 nous classons les impacts de légères variations de séquences des microARN sur la fonction naturelle de ceux-ci. Au chapitre 3 nous identifions des fenêtres dans de longs ARN dont les structures dynamiques occupent possiblement des rôles dans les désordres du spectre autistique et dans la polarisation des œufs de certains batraciens (Xenopus spp.). / Recent experimental evidence indicates that RNA structure changes, sometimes very rapidly and that these changes are both required for biochemical activity and captured by the secondary structure prediction software MC-Fold. RNA structure is thus dynamic. We compared RNA sequences from the point of view of their structural dynamics so as to investigate how similar their biochemical activities were by computing a signature from the output of the structure prediction software MC-Fold. This required us to accelerate considerably the software MC-Fold. The algorithmic approach to this acceleration is described in chapter 1. In chapter 2, point mutations that disrupt the biochemical activity of microRNA are explained in terms of changes in RNA dynamics. Finally, in chapter 3 we identify dynamic structure windows in long RNA with potentially significant roles in autism spectrum disorders and separately in Xenopus ssp. (species of frogs) egg polarisation.

Le but de ce projet était de développer des méthodes d'assemblage de novo dans le but d'assembler de petits génomes, principalement bactériens, à partir de données de séquençage de nouvelle-génération. Éventuellement, ces méthodes pourraient être appliquées à l'assemblage du génome de StachEndo, une Alpha-Protéobactérie inconnue endosymbiote de l'amibe Stachyamoeba lipophora. Suite à plusieurs analyses préliminaires, il fut observé que l’utilisation de lectures Illumina avec des assembleurs par graphe DeBruijn produisait les meilleurs résultats. Ces expériences ont également montré que les contigs produits à partir de différentes tailles de k-mères étaient complémentaires pour la finition des génomes. L’ajout de longues paires de lectures chevauchantes se montra essentiel pour la finition complète des grandes répétitions génomiques. Ces méthodes permirent d'assembler le génome de StachEndo (1,7 Mb). L'annotation de ce génome permis de montrer que StachEndo possède plusieurs caractéristiques inhabituelles chez les endosymbiotes. StachEndo constitue une espèce d'intérêt pour l'étude du développement endosymbiotique. / The goal of this project was to develop de novo genome assembly methods adapted to small genomes, especially bacterial, using next-generation sequencing data. Eventually, these methods could be used to assemble the genome of StachEndo, an unknown Alpha-Proteobacteria ensymbiont of the Stachyamoeba lipophora amoeba. Preliminary findings showed that the use of Illumina reads with DeBruijn graph assemblers yielded the best results. These experiments also showed that contigs produced with k-mers of various sizes were complementary in genome finishing assays. The addition of long-range paired-end reads proved necessary to fully close genomic assembly gaps. These methods made the assembly of StachEndo’s genome (1.7 Mb) possible. Through the annotation of StachEndo’s genes, several features that are unusal for endosymbionts were identified. StachEndo seems to be an interesting species for the study of endosymbiotic evolution.