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)

Les processus Markoviens continus en temps sont largement utilisés pour tenter d’expliquer l’évolution des séquences protéiques et nucléotidiques le long des phylogénies. Des modèles probabilistes reposant sur de telles hypothèses sont conçus pour satisfaire la non-homogénéité spatiale des contraintes fonctionnelles et environnementales agissant sur celles-ci. Récemment, des modèles Markov-modulés ont été introduits pour décrire les changements temporels dans les taux d’évolution site-spécifiques (hétérotachie). Des études ont d’autre part démontré que non seulement la force mais également la nature de la contrainte sélective agissant sur un site peut varier à travers le temps. Ici nous proposons de prendre en charge cette réalité évolutive avec un modèle Markov-modulé pour les protéines sous lequel les sites sont autorisés à modifier leurs préférences en acides aminés au cours du temps. L’estimation a posteriori des différents paramètres modulants du noyau stochastique avec les méthodes de Monte Carlo est un défi de taille que nous avons su relever partiellement grâce à la programmation parallèle. Des réglages computationnels sont par ailleurs envisagés pour accélérer la convergence vers l’optimum global de ce paysage multidimensionnel relativement complexe. Qualitativement, notre modèle semble être capable de saisir des signaux d’hétérogénéité temporelle à partir d’un jeu de données dont l’histoire évolutive est reconnue pour être riche en changements de régimes substitutionnels. Des tests de performance suggèrent de plus qu’il serait mieux ajusté aux données qu’un modèle équivalent homogène en temps. Néanmoins, les histoires substitutionnelles tirées de la distribution postérieure sont bruitées et restent difficilement interprétables du point de vue biologique. / Time-continuous Markovian process are widely used to understand the mechanism of nucleotidic acids and proteins evolution along phylogeny. Already existing probabilistic models based on such hypothesis are designed to satisfy the non-homogeneity of functional and environmental constraints acting across those biological sequences. Recently, Markov-modulated models have been introduced to describe site-specific temporal rate variation (heterotachy). Moreover, studies have demonstrated that not only strength but also the nature of the constraint acting on a specific site can vary over time. Here we propose to accommodate this evolutionary reality with a Markov-modulated model for proteins under which sites are authorized to change their amino acids propensities across time. Posterior estimation of the stochastic kernel hidden parameters with Monte Carlo methods is a challenging approach that we partially overcome with parallel computing. Fine-tuning are otherwise planned to accelerate convergence toward the target posterior stationnary distribution. Qualitatively, our model seems to be able to capture temporal heterogeneity from real sequences data sets whose evolutionary history is assumed to be rich in substitutional switch events. Furthermore, evaluation of the model performance suggest that he provides a better fit to the data set than the time-homogeneous equivalent model. Nonetheless, substitutional histories sampled from the posterior distribution are quite noisy and remain difficult to interpret biologically.

No description available.

No description available.

L'identification de gènes ayant permis à des populations de s'adapter à leur environnement local constitue une des problématiques majeures du domaine de la génétique des populations. Les méthodes statistiques actuelles répondant à cette problématique ne sont plus adaptées aux données de séquençage nouvelle génération (NGS). Nous proposons dans cette thèse de nouvelles statistiques adaptées à ces nouveaux volumes de données, destinées à la détection de gènes sous sélection. Nos méthodes reposent exclusivement sur l'Analyse en Composantes Principales, dont nous justifierons l'utilisation en génétique des populations. Nous expliquerons également les raisons pour lesquelles nos approches généralisent les méthodes statistiques existantes et démontrons l'intérêt d'utiliser une approche basée sur l'Analyse en Composantes Principales en comparant nos méthodes à celles de l'état de l'art. Notre travail a notamment abouti au développement de pcadapt, une librairie R permettant l'utilisation de nos statistiques de détection sur des données génétiques variées. / Identifying genes involved in local adaptation is of major interest in population genetics. Current statistical methods for genome scans are no longer suited to the analysis of Next Generation Sequencing (NGS) data. We propose new statistical methods to perform genome scans on massive datasets. Our methods rely exclusively on Principal Component Analysis which use in population genetics will be discussed extensively. We also explain the reasons why our approaches can be seen as extensions of existing methods and demonstrate how our PCA-based statistics compare with state-of-the-art methods. Our work has led to the development of pcadapt, an R package designed for outlier detection for various genetic data.

Les gliomes sont les principales tumeurs primitives du cerveau affectant environ 4000 nouveaux patients par an en France. La moitié des gliomes est détectée au stade avancé de glioblastome (grade IV) tandis que 15% des tumeurs sont diagnostiquées au stade II de gliomes diffus dit de bas grade. Ces tumeurs affectent des patients jeunes et présentent des mutations caractéristiques, notamment une mutation pour l’enzyme IDH1 communément retrouvée dans les glioblastomes secondaires. Ces tumeurs de bas grade sont traitées par une chirurgie, idéalement en condition éveillée mais du fait de leur nature diffuse, la partie résiduelle progressera inexorablement vers un stade III ou IV avec une survie globale entre 5 ans et 15 ans après diagnostique. La progression tumorale est hautement variable et non prédictible d’un patient à l’autre. Des foyers de progression tumorale chez 20% des patients atteints de gliome diffus de bas grade ont été identifiés. Ces foyers montrent une densité cellulaire plus élevée ainsi qu’un Ki67 augmenté. Mon travail de thèse aura consisté à étudier les modifications cellulaires et moléculaires associées à ces foyers de progression tumorale. À partir du profil ARN des foyers et des territoires adjacents, j’ai pu mettre en évidence par des techniques haut-débit la baisse d’expression significative de gènes dans les foyers notamment de AGXT2L1/ETNPPL, carboxypeptidase E, EDNRB, SFRP2. J’ai émis l’hypothèse que SFRP2 et ETNPLL pourraient s’opposer à la prolifération cellulaire et que leur diminution dans les foyers ouvrirait la voie à la transformation tumorale. Une corrélation inverse entre la quantité d’ETNPPL enzyme et la survie de patients atteints d’hépatocarcinomes a été publiée. En limitant la quantité de précurseurs de phospholipides dans la cellule, ETNPPL pourrait agir comme un frein en s’opposant à la prolifération et de fait, sa diminution dans les foyers de transformation des gliomes pourrait lever cette inhibition. Mes travaux auront été innovants tant dans leur approche comparative des différents compartiments tumoraux pour chaque patient étudié et auront révélés ETNPPL comme corrélé à la gliomagenèse et potentielle cible thérapeutique. / Gliomas are the main primary brain tumours affecting around 4000 new patients in France each year. Half of gliomas are detected in the advanced stage of glioblastoma (grade IV) while 15% of tumours are diagnosed in stage II (diffuse low-grade gliomas-DLGG). These tumors affect young patients and bear characteristic mutations, including a mutation for the enzyme IDH1 commonly found in secondary glioblastomas. These low-grade tumours are treated by surgery, ideally in awake condition but due to their diffuse nature, the residual part will progress inexorably to stage III or IV with overall survival between 5 and 15 years after diagnosis. Tumor progression is highly variable and unpredictable from one patient to another. Foci of tumor progression have been identified in 20% of patients with DLGG. These foci show a higher cell density and an increased Ki67. My thesis work consisted in studying the cellular and molecular changes associated with tumor progression. From the RNA profile of the foci and adjacent territories, I was able to highlight through high-throughput techniques significant decrease in gene expression in the foci, particularly of AGXT2L1/ETNPPL, carboxypeptidase E, EDNRB, SFRP2. I hypothesized that SFRP2 and ETNPLL could oppose cell proliferation and that their decrease would pave the way for tumor transformation. An inverse correlation between the amount of ETNPPL and the survival of patients with hepatocarcinoma has been published. By limiting the amount of phospholipid precursors in the cell, ETNPPL could act as a brake against proliferation and indeed, its decrease in glioma transformation foci could remove this inhibition. My PhD work will have been innovative in the comparative approach of the different tumors’ compartments for each patient studied and will have revealed ETNPPL as correlated to gliomagenesis and as potential therapeutic target.

Le diagnostic, la caractérisation et l'identification rapides et précis des agents pathogènes sont essentiels pour guider le traitement, détecter les événements de transmission ou les échecs de traitement. Cependant le monde biomédical est confronté à des pathogènes émergents et ré-émergents. Ainsi certaines souches bactériennes cliniques présentent des spécificités de virulence, contagiosité et/ou de résistance aux antibiotiques. Le séquençage génomique à haut débit et l’analyse comparative des génomes bactériens constituent une bonne stratégie pour étudier rapidement les caractéristiques de ces pathogènes émergents. En à peine un peu plus de 20 ans, la génomique a connu un développement considérable grâce aux nouvelles technologies de séquençage à haut débit et à l’intérêt des scientifiques, qui ont permis l’augmentation exponentielle du nombre de génomes bactériens séquencés et disponibles dans les bases de données publiques. La génomique en temps-réel consiste en une analyse rapide du génome d’une souche bactérienne clinique pour identifier les déterminants génétiques de ses caractéristiques phénotypiques inhabituelles. C’est ainsi que les objectifs de ce projet de thèse étaient : d’exploiter rapidement les données de séquençage de génomes complets pour déterminer les répertoires de résistance et de virulence ; de comparer les génomes provenant des bactéries cliniques atypiques à ceux d’autres bactéries des mêmes espèces pour identifier leurs caractéristiques spécifiques ; d’utiliser les génomes comme outil taxonomique pour décrire rapidement les nouvelles espèces bactériennes isolées dans le laboratoire par culturomique. / Rapid and accurate diagnosis, characterization and identification of pathogens are essential to guide treatment and detect transmission events or treatments failures. However, the biomedical field is confronted with emerging and re-emerging pathogens. Some of these clinical bacterial strains exhibit specificities concerning the virulence, contagiousness and / or resistance to antibiotics. High-throughput sequencing and comparative analysis of bacterial genomes is a reliable strategy enabling the rapid study of the characteristics of these emerging pathogens. In a short period, not exceeding 20 years, genomics has known a considerable revolution. In effect the introduction of the new high-throughput sequencingtechnologies and the increased concern of the scientist into this field, led to an exponential increase of number of available sequenced bacterial genomes in public databases. Real-time genomics is a strategy consisting on rapid analysis of the genome of a clinical bacterial strain in order to identify the genetic determinants justifying its unusual phenotypic characteristics. Thus, the objectives of this thesis project were: to rapidly exploit whole-genome sequencing data for identification of the virulence or resistance repertoire; to compare genomes from atypical clinical bacteria to those of other bacteria of the same species in order to identify their specific features; to use genomes as a taxonomic tool to rapidly describe the new bacterial species isolated in the laboratory by culturomics approach.

An important problem in bioinformatics is the reconstruction of gene regulatory networks from expression data. The analysis of genomic data stemming from high- throughput technologies such as microarray experiments or RNA-sequencing faces several difficulties. The first major issue is the high variable to sample ratio which is due to a number of factors: a single experiment captures all genes while the number of experiments is restricted by the experiment’s cost, time and patient cohort size. The second problem is that these data sets typically exhibit high amounts of noise.<p><p>Another important problem in bioinformatics is the question of how the inferred networks’ quality can be evaluated. The current best practice is a two step procedure. In the first step, the highest scoring interactions are compared to known interactions stored in biological databases. The inferred networks passes this quality assessment if there is a large overlap with the known interactions. In this case, a second step is carried out in which unknown but high scoring and thus promising new interactions are validated ’by hand’ via laboratory experiments. Unfortunately when integrating prior knowledge in the inference procedure, this validation procedure would be biased by using the same information in both the inference and the validation. Therefore, it would no longer allow an independent validation of the resulting network.<p><p>The main contribution of this thesis is a complete computational framework that uses experimental knock down data in a cross-validation scheme to both infer and validate directed networks. Its components are i) a method that integrates genomic data and prior knowledge to infer directed networks, ii) its implementation in an R/Bioconductor package and iii) a web application to retrieve prior knowledge from PubMed abstracts and biological databases. To infer directed networks from genomic data and prior knowledge, we propose a two step procedure: First, we adapt the pairwise feature selection strategy mRMR to integrate prior knowledge in order to obtain the network’s skeleton. Then for the subsequent orientation phase of the algorithm, we extend a criterion based on interaction information to include prior knowledge. The implementation of this method is available both as part of the prior retrieval tool Predictive Networks and as a stand-alone R/Bioconductor package named predictionet.<p><p>Furthermore, we propose a fully data-driven quantitative validation of such directed networks using experimental knock-down data: We start by identifying the set of genes that was truly affected by the perturbation experiment. The rationale of our validation procedure is that these truly affected genes should also be part of the perturbed gene’s childhood in the inferred network. Consequently, we can compute a performance score / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The dissertation covers two problems motivated by computational biology: genome rearrangements, and haplotype networks.<p><p>Genome rearrangement problems are a particular case of edit distance problems, where one seeks to transform two given objects into one another using as few operations as possible, with the additional constraint that the set of allowed operations is fixed beforehand; we are also interested in computing the corresponding distances between those objects, i.e. merely computing the minimum number of operations rather than an optimal sequence. Genome rearrangement problems can often be formulated as sorting problems on permutations (viewed as linear orderings of {1,2,n}) using as few (allowed) operations as possible. In this thesis, we focus among other operations on ``transpositions', which displace intervals of a permutation. Many questions related to sorting by transpositions are open, related in particular to its computational complexity. We use the disjoint cycle decomposition of permutations, rather than the ``standard tools' used in genome rearrangements, to prove new upper bounds on the transposition distance, as well as formulae for computing the exact distance in polynomial time in many cases. This decomposition also allows us to solve a counting problem related to the ``cycle graph' of Bafna and Pevzner, and to construct a general framework for obtaining lower bounds on any edit distance between permutations by recasting their computation as factorisation problems on related even permutations.<p><p>Haplotype networks are graphs in which a subset of vertices is labelled, used in comparative genomics as an alternative to trees. We formalise a new method due to Cassens, Mardulyn and Milinkovitch, which consists in building a graph containing a given set of partially labelled trees and with as few edges as possible. We give exact algorithms for solving the problem on two graphs, with an exponential running time in the general case but with a polynomial running time if at least one of the graphs belong to a particular class.<p>/<p>La thèse couvre deux problèmes motivés par la biologie: l'étude des réarrangements génomiques, et celle des réseaux d'haplotypes.<p><p>Les problèmes de réarrangements génomiques sont un cas particulier des problèmes de distances d'édition, où l'on cherche à transformer un objet en un autre en utilisant le plus petit nombre possible d'opérations, les opérations autorisées étant fixées au préalable; on s'intéresse également à la distance entre les deux objets, c'est-à-dire au calcul du nombre d'opérations dans une séquence optimale plutôt qu'à la recherche d'une telle séquence. Les problèmes de réarrangements génomiques peuvent souvent s'exprimer comme des problèmes de tri de permutations (vues comme des arrangements linéaires de {1,2,n}) en utilisant le plus petit nombre d'opérations (autorisées) possible. Nous examinons en particulier les ``transpositions', qui déplacent un intervalle de la permutation. Beaucoup de problèmes liés au tri par transpositions sont ouverts, en particulier sa complexité algorithmique. Nous nous écartons des ``outils standards' utilisés dans le domaine des réarrangements génomiques, et utilisons la décomposition en cycles disjoints des permutations pour prouver de nouvelles majorations sur la distance des transpositions ainsi que des formules permettant de calculer cette distance en temps polynomial dans de nombreux cas. Cette décomposition nous sert également à résoudre un problème d'énumération concernant le ``graphe des cycles' de Bafna et Pevzner, et à construire une technique générale permettant d'obtenir de nouvelles minorations en reformulant tous les problèmes de distances d'édition sur les permutations en termes de factorisations de permutations paires associées.<p><p>Les réseaux d'haplotypes sont des graphes dont une partie des sommets porte des étiquettes, utilisés en génomique comparative quand les arbres sont trop restrictifs, ou quand l'on ne peut choisir une ``meilleure' topologie parmi un ensemble donné d'arbres. Nous formalisons une nouvelle méthode due à Cassens, Mardulyn et Milinkovitch, qui consiste à construire un graphe contenant tous les arbres partiellement étiquetés donnés et possédant le moins d'arêtes possible, et donnons des algorithmes résolvant le problème de manière optimale sur deux graphes, dont le temps d'exécution est exponentiel en général mais polynomial dans quelques cas que nous caractérisons.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

High-throughput gene expression data have been generated on a large scale by biologists.<p>The thesis describe a set of tools for the analysis of such data. It is specially gearded towards microarray data. / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished