Les travaux de cette thèse portent principalement sur le développement d'une méthodologie pour la modélisation de systèmes biologiques. Cette méthodologie, basée sur une modélisation en équations différentielles, intègre aussi bien des méthodes formelles (solveur sur intervalles, solveur de formules STL), qu'analytiques (calcul de stabilité d'état stationnaire) ou numériques (algorithme d'optimisation, analyses statistiques). Elle permet l'intégration de différents types de données, telles la réponse comportementale à une perturbation ou des données quantitatives (demie-vie, concentrations). En collaboration avec une équipe de biologistes, cette méthodologie est appliquée, avec succès, au système de l'homéostasie du fer : nous étudions la réponse intracellulaire du système, via des protéines régulatrices spécifiques (protéines IRP), face à une situation de carence en fer. Un résultat majeur de cette étude est l'amélioration des connaissances sur la concentration de fer intracellulaire nécessaire à la prolifération des cellules : cette concentration est mise en avant par l'étude du modèle, puis est confirmée expérimentalement.Le deuxième volet de ces travaux portent sur le développement d'un outil pour la modélisation de réseaux de gènes avec le formalisme des réseaux de Thomas. Cet outil, développé en ASP (Answer Set Programming), permet l'intégration de différents types de données telles des données sur des mutants ou l'existence de différents états stationnaires. Cet outil permet d'éviter automatiquement l'incohérence en cas de contradiction entre différentes hypothèses sur le système. Il permet également l'inférence de propriétés biologiques telles que l'ordre entre paramètres cinétiques. / The major part of this PhD consists in the creation of a methodology to model biological systems. This methodology considers models based on differential equations, and uses formal methods (interval solver, verification of STL formula), analytical methods (study of stability) and numerical methods (optimization algorithm, statistical analysis). Moreover, many kind of data, like behavioral response to perturbation, or quantitative data (metabolite half-life and concentration) can be incorporated. In collaboration with a biologist team, this methodology is successfully applied to the iron homeostasis network : we study the response of the system to an iron depletion, at the intracellular level, based on specific regulatory proteins (IRP proteins). A major output of this study is insight into the level of iron cells need to proliferate : this concentration is pointed out by the study of the model, and is experimentally validated.The second part of the PhD is the creation of a tool to model genetic regulatory networks, using Thomas' formalism. This tool, developed using ASP (Answer Set Programming) programming language, can integrate many kind of data, like mutation data, or the existence of many steady states. It automatically avoids inconsistency in case of contradiction between different hypotheses. It also infers biological properties such as relationships between kinetic parameters.

L'épissage alternatif est un processus biologique qui génère la diversité du protéome malgré le nombre limité de gène. Ce mécanisme régule à la fois les gènes de manières qualitatives (isoformes exprimées) mais aussi quantitatives (niveau d'expression). Avec le développement des technologies de séquençage à haut débit, il est maintenant possible d'étudier à large échelle les aspects quantitatif et qualitatif du transcriptome avec une même expérience (RNA-seq). Durant ma thèse, j'ai développé une nouvelle méthode d'analyse de l'épissage alternatif dans les données RNA-seq. J'ai également participé à la mise en place du pipeline global d'analyse de données RNA-seq (expression et épissage) qui a été utilisé pour analyser un grand nombre de jeux de données. Dans un second temps, nous avons comparé notre outil d'analyse de l'épissage, FaRLine, qui est basé sur l'alignement sur un génome de référence, à KisSplice, une méthode basée sur l'assemblage. Nous avons montré que ces méthodes trouvaient un grand nombre d'événements en communs (70%), mais qu'il existait des différences non négligeables dues à la méthodologie. Nous avons analysé et classifié ces événements en 4 grandes catégories. Les variants faiblement exprimés et les exons chevauchant des éléments répétés sont mieux annotés par les méthodes basées sur l'alignement. Alors que les méthodes basées sur l'assemblage trouvent des nouveaux variants (exons ou sites d'épissage non annotés) et prédisent de l'épissage alternatif dans les famille de gènes paralogues. Notre travail souligne les points qui nécessitent encore l'amélioration des méthodes bioinformatiques. Enfin, j'ai participé au développement de méthodes permettant d'aider les biologistes à évaluer l'impact fonctionnel de modification d'épissage, que ce soit au niveau de la protéine produite (annotation des domaines protéiques au niveau des exons), ou à un niveau plus global en intégrant les modifications d'épissage dans les voies de signalisation / Alternative splicing is the biological process that explain the large diversity of the proteome compared to the limited number of genes. This process allow a qualitative regulation (expressed isoforms) and a quantitative regulation (expression level). The growth of high-trhoughtput sequencing methods enabled the analysis of these two aspects (quantitative and qualitative regulation) with the same experiment (RNA-Seq). During my PhD, I developped a new tool to analyse alternative splicing from RNA-Seq data. I also participated in the automatisation of the complet pipeline of RNA-Seq analysis (expression and splicing). This pipeline has been used to analyse various datasets. Then, we compared our mapping-first tool, FaRLine, with an assembly-first method, KisSplice. We found that the predictions of the two pipelines overlapped (70\% of exon skipping events were common), but with noticeable differences. The mapping-first approach allowed to find more lowly expressed splicing variants, and was better in predicting exons overlapping repeated elements. The assembly-first approach allowed to find more novel variants, including novel unannotated exons and splice sites. It also predicted AS in families of paralog genes. Our work point out where the bioinformatic improvment are still needed. Finally, I participated in the developpement of bioinformatics methods to help biologists to evualuate the fonctionnal impact of splicing alteration : at the level of the protein product by annotating fonctionnal domain at the exon level or at a more global level, by integrating splicing modifications in signaling pathways

La résonance magnétique nucléaire (RMN) est devenue une des techniques spectroscopiques les plus puissantes et polyvalentes de la chimie analytique avec des applications multiples dans des différents domaines de la recherche. Cependant, un des inconvénients majeurs de la RMN est le processus fastidieux d'analyse de donnée qui nécessite fréquemment des interventions humaines. Ces dernières font diminuer non seulement l'efficacité et l'objectivité des études mais également renferment les champs d'applications potentielles de la RMN pour les non-initiés. Par conséquent, le développement des méthodes computationnelles non supervisées se trouve nécessaire. Les travaux réalisés ici représentent des nouvelles approches dans le domaine de la métabolomique et de la biologie structurelle. Le défi ultime de la RMN métabolomique est l'identification complète de l'ensemble des molécules constituant les échantillons biologiques complexes. Cette étape est vitale pour toute interprétation biologique. Dans la première partie de cette thèse, une nouvelle méthode numérique a été développée pour analyser des spectres à deux dimensions HSQC et TOCSY afin d'identifier les métabolites. La performance de cette nouvelle méthode a été démontrée avec succès sur les données synthétiques et expérimentales. La RMN est une des principales techniques analytiques de la biologie structurale. Le processus conventionnel de détermination structurelle est bien établie avec souvent une attribution explicite des signaux. Dans la seconde partie de cette thèse, une nouvelle approche computationnelle est présentée. Cette nouvelle méthode permet de déterminer les structures RMN sans attributions explicites des signaux. Ces derniers proviennent de données spectrales tridimensionnelles TOCSY et NOESY. Les structures ont été résolues en appliquant cette nouvelle méthode aux données spectrales d'une protéine de 12kDa. / Nuclear Magnetic Resonance (NMR) has become one of the most powerful and versatile spectroscopic techniques in analytical chemistry with applications in many disciplines of scientific research. A downside of NMR is however the laborious data analysis workflow that involves many manual interventions. Interactive data analysis impedes not only on efficiency and objectivity, but also keeps many NMR application fields closed for non-experts. Thus, there is a high demand for the development of unsupervised computational methods. This thesis introduces such unattended approaches in the fields of metabonomics and structural biology. A foremost challenge to NMR metabolomics is the identification of all molecules present in complex metabolite mixtures that is vital for the subsequent biological interpretation. In this first part of the thesis, a novel numerical method is proposed for the analysis of two-dimensional HSQC and TOCSY spectra that yields automated metabolite identification. Proof-of principle was successfully obtained by evaluating performance characteristics on synthetic data, and on real-world applications of human urine samples, exhibiting high data complexity. NMR is one of the leading experimental techniques in structural biology. However the conventional process of structure elucidation is quite elaborated. In this second part of the thesis, a novel computational approach is presented to solve the problem of NMR structure determination without explicit resonance assignment based on three-dimensional TOCSY and NOESY spectra. Proof-of principle was successfully obtained by applying the method to an experimental data set of a 12-kilodalton medium- sized protein.

Pas de résumé / No abstract

L'annotation fonctionnelle de mutations somatiques est un point focal des études de génomique du cancer. Jusque récemment, la recherche s'est concentré sur des mutations dans la fraction codante du génome, pour lesquelles de puissants outils bioinformatiques ont été développés afin de distinguer des mutations délétères des mutations neutres. On identifie un nombre croissant de variants associés à des maladies dans le génome non-codant. L'interprétation des mutations non-codantes dans le cancer est donc devenue une tâche urgente. Des projets de grande envergure tels que ENCODE ont rendu possible l'interprétation fonctionnelle de variants dans les cancers. Plusieurs programmes ont été produits sur la base de ces informations fonctionnelles. Ces outilssont encore limités, notamment, une bas précision de la prédiction, le manque d'information de la mutation de cancer et biais de constatation importante. Dans le chapitre 2 de cette thèse, pour interpréter fonctionnellement les mutations non-codantes dans les cancers, nous avons développé deux modèles de forêts aléatoires indépendants, appelées SNP et SOM. Compte tenu de la combinaison de caractéristiques fonctionnelles à une position donnée du génome, le modèle SNP prédit la fraction de SNP rares (une mesure de la sélection négative), et le modèle SOM prédit la densité de mutations somatiques attendue à cette position. Nous avons appliqué nos deux modèles pour évaluer des clinvariant and HGMD variants asociés à des maladies, et un ensemble de SNP-contrôle aléatoires. Les résultats ont montré que les variants associés à des maladies ont des scores plus élevés que les SNP-contrôle avec le modèle SNP et inférieures avec le modèle SOM, confortant notre hypothèse selon laquelle la sélection négative, telle que mesurée par fraction de SNP rares et de densité de mutation somatiques, nous informe sur l'impact fonctionnel des mutations tumorales dans le génome non-codant. Jusqu'à présent, les chercheurs ont surtout considéré les gènes protéiques comme critiques dans l'initiation et la progression des cancers. Toutefois, des preuves récentes ont montré que les ARN non-codants, en particulier les lncRNAs, sont activement impliqués dans divers processus de cancer. Un chapitre de cette thèse est consacré à cette classe de transcripts non codants. Comme pour les gènes codants, il pourrait exister un grand nombre de lncRNAs driver de cancer. Le développement d'outils bioinformatiques pour identifier et hiérarchiser les lncRNA et autres ARN non-codants est devenu un important objet de recherche en oncologie.La dernière partie de cette thèse est consacrée à la mise en œuvre de méthodes pour découvrir des éléments non-codants potentiellement driver de cancer. Nous avons d'abord appliqué trois outils tierces, CADD, funSeq2, GWAVA, ainsi que nos modèles SNP et SOM, pour évaluer l'impact des mutations non-codantes dans tout le génome. Pour chaque locus, nous calculons la moyenne des scores de tous les variants observés à l'aide de l'un des modèles, et nous prenons au hasard le même nombre de variants et calculons leur score moyen 1 million de fois pour former une distribution nulle et obtenir une P-valeur pour ce locus. Pour valider notre hypothèse et notre modèle de permutation, nous avons testé ce système sur 452 gènes codants et 61 lncRNA liés au cancer, en utilisant des données de mutation somatique de cancer du foie, cancer du poumon, CLL et mélanome. Nous avons constaté que les lncRNAs et gènes codants associés au cancer avaient des valeurs-P significativement plus faibles que l'ensemble de lncRNAs et gènes codant. Appliquer ce test de permutation à des lncRNAs avec cinq systèmes de notation différents nous a permis de prioriser les centaines de candidats potentiellement liés au cancer.Ces candidats peuvent maintenant être soumis à validation expérimentale. / Functional annotation of somatic mutations have been a consistent hotspot of cancer genomics studies. In the past, researchers preferentially focused on mutations in the coding fraction of the genome, for which ample bioinformatics tools were developed to distinguish cancer-driver mutations from neutral ones. In recent years, as an increasing number of variants were being identified as disease-associated in the non-coding genome, interpreting non-coding cancer mutations has become an urgent task. The completion of large scale projects such as ENCODE, has made functional interpretation of cancer variants achievable, and several programs were produced based on this functional information. However, there still exists some limitations as to these prediction tools, such as low prediction accuracy, lack of cancer mutation information and significant ascertainment bias. In chapter 2 of this thesis, in order to functionally interpret non-coding mutations in cancer, we developed two independent random forest models, referred to as SNP and SOM. Given a combination of features at a given genome positions, the SNP model predicts the expected fraction of rare SNPs (a measure of negative selection), and the SOM model predicts the expected mutation density at this position. We applied our two models to score these non-coding disease-associated clinvariant and HGMD variants and a set of random control SNPs. Results showed that disease-associated variants were scored higher than control SNPs with the SNP model and lower than control SNPs with the SOM model, supporting our hypothesis that purifying selection as measured by fraction of rare SNPs and mutation density is informative for the evaluation of the functional impact of cancer mutations in the non-coding genome. In the past, researchers have preferentially considered protein-coding genes as critical to the initiation and progression of cancers. However, recent evidences have shown that ncRNAs, in particular lncRNAs, are actively implicated in various cancer processes. A chapter of this thesis is devoted to this class of non-coding transcripts. Similar to protein coding genes, there might be a large number of lncRNAs with cancer-driving functions. The development of bioinformatics tools to prioritize them has become a new focus of research for computational oncologists.The last part of this thesis is devoted to the implementation of methods for discovering potential cancer-driving non-coding elements in lncRNA and protein-coding genes. We applied three scoring tools, CADD, funSeq2, GWAVA, together with our SNP and SOM scoring systems to prioritize cancer-associated elements using a permutation-based algorithm. For each locus, we compute the average score of all observed variants using one of the models, and we randomly take the same number of variants and compute their average score 1 million times to form a null distribution and obtain a P value for this locus. To validate our hypothesis and permutation model, we tested this system on 61 cancer-related lncRNA and 452 cancer genes using somatic mutation data from liver cancer, lung cancer, CLL and melanoma. We observed that both cancer lncRNAs and protein-coding genes had significantly lower average P values than total lncRNAs and protein-coding genes in all cases. Applying the permutation test to lncRNAs with five different scoring systems enabled us to prioritize hundreds to thousands of cancer-related lncRNA candidates. These candidates can be used for future experimental validation.

Ces travaux de thèse reposent sur le double objectif de proposer des approches innovantes pour l’étude des relations entre un hôte et son microbiote, et de les appliquer à la description fine de l’holobionte du puceron du pois par des données métagénomiques. Les relations symbiotiques façonnent le fonctionnement et l’évolution de tous les organismes, mais restent décrites de manière imparfaite, notamment à cause de la difficulté à caractériser la diversité génomique des partenaires microbiens constitutifs des holobiontes. L’essor des technologies de séquençage métagénomique révolutionne l’étude de ces systèmes, mais pose également des problèmes méthodologiques pour analyser les jeux de données métagénomiques. La métagénomique est ici appliquée au puceron du pois, un modèle d’étude des relations symbiotiques qui abrite une communauté bactérienne d’une complexité modérée, idéale pour développer de nouvelles approches de caractérisation de la diversité microbienne. Cette thèse vise à mieux décrire la communauté de symbiotes qu’abrite cet holobionte, notamment en distinguant les différents niveaux de variabilité génomique en son sein. Nous présentons une démarche pour l’analyse métagénomique d’holobiontes, qui repose d’abord sur l’assignation taxonomiques des lectures par alignement à des génomes de référence ou préalablement assemblés, puis sur la recherche de variants génomiques. L’étude de génotypes complets de symbiotes permet de retracer l’histoire évolutive des relations hôte-microbiote avec une résolution élevée. Chez le puceron du pois, nous mettons en évidence des niveaux et structures de diversité génomique différents selon les symbiotes, que nous proposons d’expliquer par les modalités de transmission ou l’histoire évolutive propre à chacun des partenaires microbiens. Cette approche repose sur la disponibilité d’un génome de référence adapté, qui est souvent difficile à obtenir en métagénomique. Dans un second temps, nous présentons donc une méthode d’assemblage guidé par référence en contexte métagénomique. Cette méthode se déroule en deux temps : le recrutement et l’assemblage de lectures par alignement sur un génome de référence distant, puis l’assemblage de novo ciblé des régions manquantes, permis par des développements complémentaires apportés au logiciel MindTheGap. Comparativement à un assembleur métagénomique, cette méthode permet l’assemblage d’un seul génome en un temps réduit, et permet de détecter d’éventuels variants structuraux sur le génome ciblé. Appliqué au puceron du pois, MindTheGap a réalisé l’assemblage du symbiote obligatoire Buchnera en un seul contig, et a permis d’identifier différents variants structuraux du bactériophage APSE. Ces travaux ouvrent la voie à la fois à une caractérisation plus précise des relations hôte-microbiote chez le puceron du pois par des approches fonctionnelles et métaboliques, ainsi qu’à l’application des outils présentés à des systèmes plus complexes. / The aim of this PhD thesis is to develop innovative approaches to characterize host-microbiota relationships, and to apply them to finely explore the pea aphid microbiota using metagenomic data. Symbiotic relationships play a major role in the life and evolution of all organisms, but are imperfectly described, essentially because of the difficult characterization of the genomic diversity of the microbial partners. The rise of high throughput metagenomic sequencing is a game changer for the study of those systems, but also raises methodological issues to analyze large metagenomic datasets. Metagenomic is here applied to the pea aphid holobiont, a model system for the study of symbiotic relationships, sheltering a moderately complex microbial community. This level of complexity seems to be ideal to develop new approaches for the strain-resolved characterization of host-microbiota relationships. This thesis aims at a better description of this symbiotic community by distinguishing several scales of metagenomic diversity. In a first part, we present a framework for the metagenomic analysis of holobionts, relying first on the taxonomic assignation of reads by alignment to reference or newly assembled genomes, and then on the detection of genomic variants. Whole genome variant profiles make possible to track the evolutionary history of host-microbiota associations with a high resolution. In the case of the pea aphid, we highlight different scales and structures for the metagenomic diversity of the different symbionts, accounting for different transmission modes or evolutionary histories specific to each microbial partner. This framework is based on the availability of a suitable reference genome, that may be hard to obtain in a metagenomic context. In a second part, we therefore present a novel method for reference guided genome assembly from metagenomic data. This method is based on two steps. First, the recruitment and assembly of reads by mapping metagenomic reads on a distant reference genome, and second, the de novo assembly of the missing regions, allowed by the development of an improved version of the software MindTheGap. Compared to a standard metagenomic assembler, this methods makes possible to assemble a single genome in a reasonable time, and allows to detect eventual structural variations within the targeted genome. When applied to the pea aphid holobiont, MindTheGap yielded single contig assemblie of the obligatory symbiont Buchnera aphidicola, and helped to identify different structural variants of the bacteriophage APSE. This works paves the way to a finer characterization of host-microbiota interactions, and to the application of the presented approaches to more complex systems.

. / In this PhD, we present some algorithms and complexity results for two general problems that arise in the analysis of a metabolic network: the search for elementary modes of a network and the search for minimal precursors sets. Elementary modes is a common tool in the study of the cellular characteristic of a metabolic network. An elementary mode can be seen as a minimal set of reactions that can work in steady state independently of the rest of the network. It has therefore served as a mathematical model for the possible metabolic pathways of a cell. Their computation is not trivial and poses computational challenges. We show that some problems, like checking consistency of a network, finding one elementary mode or checking that a set of reactions constitutes a cut are easy problems, giving polynomial algorithms based on LP formulations. We also prove the hardness of central problems like finding a minimum size elementary mode, finding an elementary mode containing two given reactions, counting the number of elementary modes or finding a minimum reaction cut. On the enumeration problem, we show that enumerating all reactions containing one given reaction cannot be done in polynomial total time unless P=NP. This result provides some idea about the complexity of enumerating all the elementary modes. The search for precursor sets is motivated by discovering which external metabolites are sufficient to allow the production of a given set of target metabolites. In contrast with previous proposals, we present a new approach which is the first to formally consider the use of cycles in the way to produce the target. We present a polynomial algorithm to decide whether a set is a precursor set of a given target. We also show that, given a target set, finding a minimal precursor set is easy but finding a precursor set of minimum size is NP-hard. We further show that finding a solution with minimum size internal supply is NP-hard. We give a simple characterisation of precursors sets by the existence of hyperpaths between the solutions and the target. If we consider the enumeration of all the minimal precursor sets of a given target, we find that this problem cannot be solved in polynomial total time unless P=NP. Despite this result, we present two algorithms that have good performance for medium-size networks

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal. / L'inférence d'un modèle tridimensionnel (3-D) d'une molécule d'ARN à partir d'informations biochimiques de faible résolution est une tâche complexe. Le développement de méthodes efficaces et objectives de modélisation est essentiel à la compréhension des mécanismes moléculaires impliquant des ARN. Le présent travail propose trois ajouts importants de ce domaine. Dans un premier temps, une définition de l'espace des conformations d'un ARN est établie et la technique de retour-arrière est décrite de façon à permettre une exploration complète de cet espace. Ensuite, un formalisme basé sur la logique floue est présenté. Cette approche permet d'utiliser l'information provenant de séquences multiples et est appliquée pour la modélisation du ribozyme activé par le plomb. Finalement, la flexibilité d'un système de modélisation 3-D utilisant une approche de satisfaction de contrainte est mise en évidence par l'ajout d'un nouveau type de contrainte dans l'engin de recherche, permettant la modélisation efficace de multimères cycliques. Ces ajouts permettent d'élargir le spectre des informations utiles à la modélisation 3-D des ARN et facilite l'intégration de nouveaux types d'informations à l'intérieur d'une méthode systématique. Les résultats obtenus sur des projets de modélisation spécifiques (ribozyme activé par le plomb et pRNA de çi>29) permettent de confirmer la pertinence de cette approche.

La quantité d'informations stockée dans les bases de données est en constante augmentation rendant ainsi nécessaire la mise au point de systèmes d'analyse et de visualisation. Nous nous intéressons dans cette thèse aux données relationnelles et plus particulièrement aux données biologiques. Cette thèse s'oriente autour de trois axes principaux : tout d'abord, la décomposition de graphes en groupes d'éléments ”similaires” afin de détecter d'éventuelles structures de communauté ; le deuxième aspect consiste à mettre en évidence ces structures dans un système de visualisation, et dans un dernier temps, nous nous intéressons à l'utilisabilité de l'un de ces systèmes de visualisation via une évaluation expérimentale.<br />Les travaux de cette thèse ont été appliqués sur des données réelles provenant de deux domaines de la biologie : les réseaux métaboliques et les réseaux d'interactions gènes-protéines.

Les récepteurs couplés aux protéines G de classe A (RCPG) constituent la plus grande famille de récepteurs transmembranaires du génome humain et sont impliqués dans la régulation de nombreux mécanismes physiologiques. Comprendre les mécanismes évolutifs qui ont conduit à la diversité de cette famille de récepteurs pourrait permettre une meilleure connaissance des relations séquence-structure-fonction des différentes sous-familles. Pour obtenir des informations sur l'évolution des RCPG, nous avons exploré leur espace de séquences par multidimensional scaling métrique (MDS). Nous avons appliqué une nouvelle technique MDS qui projette des séquences supplémentaires sur un espace de référence et permet ainsi la comparaison des séquences de différentes espèces. Les résultats montrent que les récepteurs se répartissent en quatre groupes et suggèrent que les récepteurs actuels ont évolué à partir d'ancêtres des récepteurs de peptides suivant trois directions évolutives principales. Les prolines des hélices transmembranaires 2 et/ou 5 sont impliquées dans deux de ces directions. Pour comprendre le mécanisme fin ayant abouti à la formation des différentes sous-familles, nous avons analysé les covariations des résidus à différents niveaux hiérarchiques (classe/groupe/sous-famille). Nous avons testé différentes méthodes pour analyser les mutations corrélées afin de sélectionner une méthode robuste pour les différents jeux de séquences. L'application de cette méthode met en évidence des résidus spécifiques qui sont cruciaux pour l'évolution de sous-familles particulières.