Les travaux présentés dans cette thèse s'inscrivent dans le cadre de l'analyse de phénomènes biologiques par des moyens informatiques, c'est-à-dire la bio-informatique. Nous nous intéressons plus particulièrement à l'analyse de séquences nucléiques. Dans ce cadre, nos travaux se décomposent en deux parties: l'identification de séquences codantes et l'identification de séquences non-codantes partageant une structure conservée telles que des ARN non-codants. L'originalité des méthodes proposées, protea et carnac, réside dans le traitement d'ensembles de séquences nucléiques faiblement conservées sans avoir recours à leur alignement au préalable. Ces méthodes s'appuient sur un même schéma global d'analyse comparative pour identifier des traces laissées par les mécanismes de sélection durant l'évolution, traces globalement cohérentes entre toutes les séquences. Nous avons évalué protea et carnac sur des données de référence pour la communauté et obtenu plusieurs résultats significatifs. Dans le cadre de travaux collaboratifs, nous présentons également deux exemples intégrations de ces logiciels. magnolia est un logiciel qui construit un alignement multiple de séquences nucléiques respectueux de leur fonction commune prédites par protea et/ou carnac. protea et \carnac sont également intégrés dans une plate-forme d'annotation automatique par génomique comparative.

Avec l'arrivée des données moléculaires vers la fin des années 70, nous avons assisté à la découverte de nouveaux mécanismes d'évolution primordiaux dont l'échange du matériel génétique entre les espèces. Un tel échange peut se faire horizontalement, quand l'organisme intègre le matériel génétique provenant d'un autre organisme qui n'est pas son descendant direct, ou verticalement, quand l'organisme reçoit du matériel génétique à partir de son ancêtre le plus proche. Le problème de la détection et de la classification des transferts horizontaux de gènes (THG) est parmi les plus ardus en bioinformatique. Dans cette thèse, nous décrivons cinq nouveaux algorithmes pour la détection de THGs complets ou partiels qui seront basés sur des comparaisons topologiques et métriques entre un arbre d'espèces et un arbre de gène inférés pour le même ensemble d'espèces. Ces algorithmes incluent l'algorithme de détection de THGs complets ainsi que ses versions interactive et consensus. Les deux algorithmes de détection de transferts partiels que nous avons proposés peuvent être vus comme une généralisation de l'algorithme de détection de transferts complets. Ils peuvent être utilisés pour identifier des gènes mosaïques. Nous présentons aussi dans cette thèse une version parallèle de l'algorithme de détection de THGs complets, ainsi qu'une plateforme pour la transformation semi-automatique de programmes bioinformatiques séquentiels en programmes parallèles. Une interface Web intégrant tous les programmes développés dans le cadre de ce projet doctoral a aussi été mise au point. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithmes bioinformatiques, arbre phylogénétique, programmation parallèle, réseau réticulé, transfert horizontal de gènes (THG).

Les travaux présentés dans cette thèse s'inscrivent dans le cadre bio-informatique de l'analyse des génomes. Plus particulièrement, ces travaux concernent l'expression des gènes et les éléments régulateurs, présents dans l'ADN, qui participent à la modulation de cette expression.<br />Le problème de la recherche de ces éléments régulateurs peut être envisagé sous l'angle informatique de la recherche de motifs approchés particuliers.<br /><br />La recherche de motifs régulateurs est une question difficile du fait de la faible spécificité des motifs recherchés. Pour pouvoir y répondre, il faut prendre en compte différentes formes d'information. En particulier, il est pertinent de prendre en compte la conservation entre espèces (génomique comparative), la conservation entre séquences génomiques partageant des éléments de régulation (gènes co-régulés) ou encore, dans certains cas, la conservation spatiale des sites de fixation.<br /><br />Dans ce cadre, nous proposons une méthode permettant de tirer parti, à la fois de la conservation spatiale, et de la conservation entre espèces. Cette approche se compose d'un algorithme de recherche locale et d'évaluateurs statistiques adaptés au problème de la recherche de motifs sur-représentés localement lorsque l'environnement de recherche est hétérogène, c'est-à-dire pour des séquences pouvant provenir d'organismes différents ou de régions différentes du génome. Ces travaux ont été mis en oeuvre dans un logiciel appelé TFM-Explorer, que nous avons évalué avec succès sur des données issues du génome humain, de la souris et du rat.

L'acide désoxyribonucléique (ADN) et l'acide ribonucléique (ARN) sont des polymères de nucléotides essentiels à la cellule. À l'inverse de l'ADN qui sert principalement à stocker l'information génétique, les ARN sont impliqués dans plusieurs processus métaboliques. Par exemple, ils transmettent l’information génétique codée dans l’ADN. Ils sont essentiels pour la maturation des autres ARN, la régulation de l’expression génétique, la prévention de la dégradation des chromosomes et le ciblage des protéines dans la cellule. La polyvalence fonctionnelle de l'ARN résulte de sa plus grande diversité structurale. Notre laboratoire a développé MC-Fold, un algorithme pour prédire la structure des ARN qu'on représente avec des graphes d'interactions inter-nucléotidiques. Les sommets de ces graphes représentent les nucléotides et les arêtes leurs interactions. Notre laboratoire a aussi observé qu'un petit ensemble de cycles d'interactions à lui seul définit la structure de n'importe quel motif d'ARN. La formation de ces cycles dépend de la séquence de nucléotides et MC-Fold détermine les cycles les plus probables étant donnée cette séquence. Mon projet de maîtrise a été, dans un premier temps, de définir une base de données des motifs structuraux et fonctionnels d'ARN, bdMotifs, en terme de ces cycles. Par la suite, j’ai implanté un algorithme, MC-Motifs, qui recherche ces motifs dans des graphes d'interactions et, entre autres, ceux générés par MC-Fold. Finalement, j’ai validé mon algorithme sur des ARN dont la structure est connue, tels que les ARN ribosomaux (ARNr) 5S, 16S et 23S, et l'ARN utilisé pour prédire la structure des riborégulateurs. Le mémoire est divisé en cinq chapitres. Le premier chapitre présente la structure chimique, les fonctions cellulaires de l'ARN et le repliement structural du polymère. Dans le deuxième chapitre, je décris la base de données bdMotifs. Dans le troisième chapitre, l’algorithme de recherche MC-Motifs est introduit. Le quatrième chapitre présente les résultats de la validation et des prédictions. Finalement, le dernier chapitre porte sur la discussion des résultats suivis d’une conclusion sur le travail. / Deoxyribonucleic acid (DNA) and ribonucleic acid (RNA) are polymers of nucleotides essential for the survival of the cell. Contrary to DNA, whose main role is to store genetic information, RNA is involved in multiple metabolic processes. For example, RNA is involved in the transfer of information from DNA to protein, the processing and modification of other RNAs, the regulation of gene expression, the end-maintenance of chromosomes, and the sorting of proteins within the cell. This functional versatility of RNA comes from its structural diversity. Our laboratory developed MC-Fold, an algorithm that predicts RNA structures by representing them with nucleotide interaction graphs. The nodes in these graphs represent the nucleotides, and the edges the interactions between them. Our laboratory also observed that a limited number of interaction cycles can define the structure of any RNA motif. The formation of these cycles is determined by the nucleotide sequence and MC-Fold determines the most likely cycles based on that sequence. In this Master Degree project, I first built a database of structural and functional RNA motifs, bdMotifs, based on their constituent cycles. Then, I implemented an algorithm, MC-Motifs, which detects motifs within interaction graphs generated either by MC-Fold or by any other method. Finally, I validated my algorithm on known RNA structures such as the 5S, 16S and 23S ribosomal RNA (rRNA) and predicted structure of riboswitches. The Master thesis is divided into five chapters. The first chapter presents the chemical structure of RNA, its cellular functions and the structural folding of the polymer. In the second chapter, the database bdMotifs is described. In the third chapter, the MC-Motifs algorithm is introduced. In the fourth chapter, I present the results of MC-Motifs. Finally, in the last chapter, I discuss theses results and I give a conclusion on the project.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Le virus de l'hépatite C (VHC) est une menace majeure avec plus de 130 millions de personnes infectées chaque année. Il constitue la principale cause de cancer du foie. Le VHC est un virus transmis par le sang soit au cours de consommation de drogue par voie intraveineuse soit lors de transfusions sanguines. Il s'adapte à l'environnement de l'hôte grâce à un taux de mutation élevé qui amoindrit l’efficacité des traitements. Le virus se multiplie rapidement dans l'hôte et crée ainsi une population de virus génétiquement hétérogènes, appelée quasi-espèces, qui peut ainsi répondre aux pressions sélectives liées au traitement. Les traitement antiviraux existants sont des tri-thérapies contenant des peg-interféron, de la ribavirine et des inhibiteurs de la protéine (PI). Les inhibiteurs comme la telaprevir ou la bocéprévir ciblent la région NS3 du génome en bloquant le mécanisme de réplication. Cependant, en raison de la nature dynamique des quasi-espèces, les séquences cibles sont variables et les inhibiteurs conçus pour se lier à une région génomique particulière sont rendus inefficaces.Nous analysons ces populations virales en utilisant les techniques modernes de séquençage et le pyroséquencage profond qui permet l’analyse à grande échelle des données génétiques. La technique “Amplicon Sequencing” permet de cibler des régions particulières du génome viral, comme les régions NS3 ou NS5B qui participent au mécanisme de réplication et qui sont des cibles pour les thérapies antivirales. Par rapport au séquençage Sanger, notre pipeline NGS permet d’appréhender l’hétérogénéité de la population virale au sein d’un hôte. Pour analyser les données NGS, nous avons implémenté un pipeline d’analyse bioinformatique qui a été automatisé avec eHive.Nous étudions des échantillons de VHC de 40 patients traités par trithérapie. Deux sources de cellules virales sont utilisées pour le séquençage: les cellules du plasma et les cellules mononuclées du sang périphérique. L'objectif est de vérifier si une analyse des mutations de la région génomique NS3 peut aider à prédire le résultat du traitement. Nous constatons que des mutations de résistance aux antiviraux se trouvent à la fois chez les individus qui ont répondu et qui n’ont pas répondu au traitement. Nous avons donc recherché d'autres signatures génétiques de l'échec du traitement. Nous constatons que l'hétérogénéité génétique est plus faible chez les individus qui répondent de manière favorable au traitement. Notre conclusion est que l'hétérogénéité virale est un facteur indépendant pour prédire la réponse à un traitement, en plus de la présence de mutations spécifiques dans les régions ciblées par le traitement.Les techniques NGS permettent également d’étudier l'évolution virale au sein d'un seul hôte. En utilisant de multiples temps d'échantillonnage, nous pouvons mesurer les caractéristiques de l'évolution de la population virale. Pour trois patients avec des échantillons viraux couvrant une période de 13 ans, nous avons utilisé la technique “Amplicon Sequencing“ pour les régions NS3 et NS5B. Des infections mixtes comprenant de multiples génotypes sont retrouvées chez deux patients. Nous avons montré qu’il existe de la structure de populations et des lignées divergentes de VHC au sein de chaque patient. Au cours du traitement, l'hétérogénéité génétique et la taille efficace de la population dans la région NS5B augmente fortement après le début du traitement. Ces résultats mettent en évidence un processus de sélection diversifiante suite au traitement qui augmente l'hétérogénéité génétique virale. Nous mettons ainsi en évidence un processus dit de balayage sélectif doux qui est observé pour la première fois chez des patients infectées par des génotypes multiples du virus VHC.Notre analyse NGS montre que l'hétérogénéité génétique du VHC est liée à l'échec ou à la réussite du traitement et que son évolution permet de mieux comprendre la façon dont les virus s'adaptent au traitement. / Hepatitis C virus (HCV) is a major threat to global health, with over 130 million annual infections. HCV is a blood borne virus transmitted primarily via intravenous drug use or hospital transfusions. It infects the liver cells and is the leading cause of liver cancer. It adapts to the host environment with a high mutation rate and can make efficient treatment very difficult. Due to poor replication proofreading, the virus multiplies rapidly in the host and creates a population of viruses which is genetically heterogeneous enough to escape selective pressures. This HCV population called quasispecies is found within and between infected hosts. Current antiviral treatment consists of a triple therapy of peg-Interferon, ribavirin and protein inhibitors (PI). PIs such as telaprevir, boceprevir target the NS3 region of the genome, blocking the replication mechanism. However due to the highly dynamic nature of the quasispecies, the target sequences are variable and PIs designed to bind to a particular genomic region are therefore rendered ineffective.We analyse viral populations of HCV using Next generation Sequencing (NGS) technologies and ultradeep pyrosequencing, which allow for rapid and large scale analysis of genetic data. Amplicon sequencing allows for targeting particular regions of the viral genome, such as the NS3 or NS5B which form a part of the replication mechanism and hence are targets for antiviral therapy. Compared to Sanger sequencing, our NGS pipeline ascertains viral population heterogeneity within a host. We implemented the bioinformatics workflow manually and in eHive as an automated pipeline.We study HCV samples from 40 patients treated with triple therapy. Two sources of the virus, plasma and peripheral blood mononuclear cells are used for sequencing. The main aim is to check if a baseline analysis of the NS3 genomic region can help to predict the outcome of the treatment. We find that antiviral resistance mutations are found in both responders and non-responders to the treatment. Since no correlation exists between observed mutations and failure of tri-therapy, we look for other genetic signatures of treatment failure. We find that genetic heterogeneity, calculated using Shannon’s entropy, is lower in responders. We conclude that the viral heterogeneity can be used as an independent factor to predict response to treatment, more than presence of specific mutations at baseline.NGS also enables large-scale studies of viral evolution within a single host. Using multiple sampling time points, we gain insights about viral evolutionary characteristics of HCV and responses to selective pressures during infection. For three patients with viral samples covering a period of 13 years, we perform amplicon sequencing on the NS3 and NS5B regions. Mixed infections comprising of multiple genotypes are found in two patients. We find considerable population structure and diverging HCV lineages within each patient. Over the course of treatment, genetic heterogeneity and effective population size in the NS5B regions increases sharply after treatment initiation compared to baseline. These results provide evidence of diversifying selection occurring post-treatment, acting on standing genetic variation resulting in high genetic heterogeneity. These are characteristics of a soft selective sweep, which is observed for the first time in chronic HCV patients infected with multiple genotypes.Our NGS analysis show that genetic heterogeneity in HCV is related to treatment failure and that its evolution provides insights about how viruses adapt to treatment.

Les voies de signalisation décrivent les réponses d'une cellule à des stimuli externes. Elles sont primordiales dans les processus biologiques tels que la différentiation, la prolifération ou encore l'apoptose. La biologie des systèmes tentent d'étudier ces voies de façon exhaustive à partir de modèles statistiques ou dynamiques. Le nombre de solutions expliquant un phénomène biologique (par exemple la réaction d'une cellule à un stimulus) peut être très élevé dans le cas de grands modèles. Cette thèse propose, dans un premier temps, différentes stratégies de regroupement de ces solutions à partir de méthodes de clustering et d'analyse de concepts formels. Puis elle présente la caractérisation de ces regroupements à partir de web sémantique. Ces stratégies ont été appliquées au réseau de signalisation du TGF-beta, un stimulus extra-cellulaire jouant un rôle important dans le développement du cancer, ce qui a permis d'identifier cinq grands groupes de trajectoires participant chacun à des processus biologiques différents. Dans un second temps, cette thèse se confronte au problème de conversion des données hétérogènes provenant de différentes bases dans un formalisme unique afin de pouvoir généraliser l'étude précédente. Elle propose une stratégie permettant de regrouper les différents réseaux de signalisation provenant d'une base de données en un modèle unique et ainsi permettant de calculer toutes les trajectoires de signalisation d'un stimulus. / Signaling pathways describe the extern stimuli responses of a cell. They are indispensable in biological processes such as differentiation, proliferation or apoptosis. The Systems Biology tries to study exhaustively the signalling pathways using static or dynamic models. The number of solutions which explain a biological phenomenon (for example the stimulus reaction of cell) can be very high in large models. First, this thesis proposes some different strategies to group the solutions describing the stimulus signalling with clustering methods and Formal Concept Analysis. Then, it presents the cluster characterization with semantic web methods. Those strategies have been applied to the TGF-beta signaling network, an extracellular stimulus playing an important role in the cancer growing, which helped to identify 5 large groups of trajectories characterized by different biological processes. Next, this thesis confronts the problem of heterogeneous data translation from different bases to a unique formalism. The goal is to be able to generalize the previous study. It proposes a strategy to group signaling pathways of a database to an unique model, then to calculate every signaling trajectory of the stimulus.

Genes can be associated in numerous ways, e.g. by co-expression in micro-arrays, co-regulation in operons and regulons or co-localization on the genome. Association of genes often indicates that they contribute to a common biological function, such as a pathway. The aim of this thesis is to predict metabolic pathways from associated enzyme-coding genes. The prediction approach developed in this work consists of two steps: First, the reactions are obtained that are carried out by the enzymes coded by the genes. Second, the gaps between these seed reactions are filled with intermediate compounds and reactions. In order to select these intermediates, metabolic data is needed. This work made use of metabolic data collected from the two major metabolic databases, KEGG and MetaCyc. The metabolic data is represented as a network (or graph) consisting of reaction nodes and compound nodes. Interme- diate compounds and reactions are then predicted by connecting the seed reactions obtained from the query genes in this metabolic network using a graph algorithm.<p>In large metabolic networks, there are numerous ways to connect the seed reactions. The main problem of the graph-based prediction approach is to differentiate biochemically valid connections from others. Metabolic networks contain hub compounds, which are involved in a large number of reactions, such as ATP, NADPH, H2O or CO2. When a graph algorithm traverses the metabolic network via these hub compounds, the resulting metabolic pathway is often biochemically invalid.<p>In the first step of the thesis, an already existing approach to predict pathways from two seeds was improved. In the previous approach, the metabolic network was weighted to penalize hub compounds and an extensive evaluation was performed, which showed that the weighted network yielded higher prediction accuracies than either a raw or filtered network (where hub compounds are removed). In the improved approach, hub compounds are avoided using reaction-specific side/main compound an- notations from KEGG RPAIR. As an evaluation showed, this approach in combination with weights increases prediction accuracy with respect to the weighted, filtered and raw network.<p>In the second step of the thesis, path finding between two seeds was extended to pathway prediction given multiple seeds. Several multiple-seed pathay prediction approaches were evaluated, namely three Steiner tree solving heuristics and a random-walk based algorithm called kWalks. The evaluation showed that a combination of kWalks with a Steiner tree heuristic applied to a weighted graph yielded the highest prediction accuracy.<p>Finally, the best perfoming algorithm was applied to a microarray data set, which measured gene expression in S. cerevisiae cells growing on 21 different compounds as sole nitrogen source. For 20 nitrogen sources, gene groups were obtained that were significantly over-expressed or suppressed with respect to urea as reference nitrogen source. For each of these 40 gene groups, a metabolic pathway was predicted that represents the part of metabolism up- or down-regulated in the presence of the investigated nitrogen source.<p>The graph-based prediction of pathways is not restricted to metabolic networks. It may be applied to any biological network and to any data set yielding groups of associated genes, enzymes or compounds. Thus, multiple-end pathway prediction can serve to interpret various high-throughput data sets. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Doctorat en Sciences / info:eu-repo/semantics/nonPublished