Le domaine scientifique de la Biologie des Systèmes étudie les interactions entre les composantes d'un système biologique afin d'en comprendre son fonctionnement global. Au cours de cette these, nous avons d’abord utilisé des graphes simples. Cette approche a permis d' appréhender la manière dont un réseau biologique peut interagir avec son environnement, lui-même modélisé par un autre réseau. Nous avons ensuite défini le formalisme MIB (Model of Interactions in Biology) qui permet de définir, rechercher et étudier les motifs hétérogènes. Enfin pour approfondir l'étude de la structure et de la dynamique, nous avons proposé le formalisme MIN. MIN possède la structure bipartie de MIB, mais permet d'avoir des annotations beaucoup plus riches des noeuds et des arcs du réseau qui peuvent être utilisées pour la traduction des données automatiquement en d'autres formalismes couramment utilisés en modélisation biologique, tels que les équations différentielles ou la modélisation logique. / The scientific domain of the Systems Biology studies the interactions between the components of a biological system in order to understand its functioning as a whole. In this thesis, we first used searched to apprehend how a biological network, modelled as a simple graph, interact with its environment, modelled by another graph. Next, we have defined the MIB formalism (for Model of Interactions in Biology) that enables to model, to search and to study the heterogeneous motifs in biological networks. Finally, for deepening the study of structure and dynamics of biological networks, we have proposed the MIN formalism (for Modular Interaction Network). MIN inherited the bipartite structure of MIB, but also includes the richer annotations for nodes, arcs and possible states of the network, thus enabling the automatic translation of data contained in MIN into other formalisms commonly used in biology for dynamics modelling, such as logical networks, differential equations or Petri nets.

Les protéines associées aux membranes sont d'une importance cruciale pour la cellule. Cependant, en raison d'une plus grande difficulté de manipulation, les données biochimiques les concernant sont très lacunaires, notamment au point de vue de la formation de complexes entre ces protéines. L'objectif global de notre travail consiste à combler ces lacunes et à préciser les interactions entre protéines membranaires chez la levure Saccharomyces cerevisiae et plus précisément, entre les transporteurs. Nous avons commencé notre travail par l'étude d'un jeu de données d'interactions à grande échelle entre toutes les perméases détectées par une méthode de double hybride spécialement adaptée aux protéines insolubles (split ubiquitin). Premièrement, la qualité des données a été estimée en étudiant le comportement global des données et des témoins négatifs et positifs. Les données ont ensuite été standardisées et filtrées de façon à ne conserver que les plus significatives. Ces interactions ont ensuite été étudiées en les modélisant dans un réseau d'interactions que nous avons étudié par des techniques issues de la théorie des graphes. Après une évaluation systématique de différentes méthodes de clustering, nous avons notamment recherché au sein du réseau des groupes de protéines densément interconnectées et de fonctions similaires qui correspondraient éventuellement à des complexes protéiques. Les résultats révélés par l'étude du réseau expérimental se sont révélés assez décevants. En effet, même si nous avons pu retrouver certaines interactions déjà décrites, un bon nombre des interactions filtrées semblait n'avoir aucune réalité biologique et nous n'avons pu retrouver que très peu de modules de protéines de fonction semblable hautement inter-connectées. Parmi ceux-ci, il est apparu que les transporteurs d'acides aminés semblaient interagir entre eux. L'approche expérimentale n'ayant eu que peu de succès, nous l'avons contournée en utilisant des méthodes de génomique comparative d'inférence d'interactions fonctionnelles. Dans un premier temps, malgré une évaluation rigoureuse, l'étude des profils phylogénétiques (la prédiction d'interactions fonctionnelles en étudiant la corrééélation des profils de présence - absence des gènes dans un ensemble de génomes), n'a produit que des résultats mitigés car les perméases semblent très peu conservées dès lors que l'on considère d'autres organismes que les extit{Fungi}. Afin d'étudier la régulation des perméases, nous avons ensuite développé et appliqué une nouvelle méthode qui permet d'inférer un réseau de co-régulation génétique sur base de la similarité des empreintes phylogénétiques découvertes dans tous les gènes de levure. Cette méthode, qui n'utilise que les séquences génomiques pour l'inférence du réseau, a donné de très bons résultats, validés extit{in silico} et expérimentalement et son application à l'ensemble des perméases a permis de retrouver plusieurs régulations bien connues, d'en inférer de nouvelles et de proposer de nouvelles pistes de recherche. En parallèle à ce travail, nous avons développé et rendu accessible NeAT un ensemble d'outils informatique consacrés à l'analyse de réseaux biologiques.

. / 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

Dans de nombreuses applications telles que la médecine, l'environnement ou les biotechnologies par exemple, la découverte de nouveau processus de régulations de gènes permet une meilleure compréhension des réponses phénotypiques des cellules à des stimuli externes. Pour cela, il est alors d'usage de générer et d'analyser les données transcriptomiques issues d'expériences de types puces à ADN ou plus récemment de RNAseq. Ainsi, pour chaque gène d'un organisme d'étude placé dans différentes conditions expérimentales, un ensemble de niveau d'expression est obtenu. A partir de ces données, les mécanismes de régulation des gènes peuvent être obtenus à travers un ensemble de liens dans des graphes. Dans ces réseaux, les nœuds correspondent aux gènes. A lien entre deux nœuds est identifié si une relation de régulation existent entre les deux gènes correspondant. De tels réseaux sont appelés Réseaux de Régulation de Gènes (RRGs). Malgré la profusion de méthodes d'inférence disponible, leur construction et leur analyse restent encore à ce jour un défi.Dans cette thèse, nous proposons de répondre au problème d'inférence de réseaux par des techniques d'optimisation dans des graphes. A partir d'information de régulation sur l'ensemble des couples de gènes, nous proposons de déterminer la présence d'arêtes dans le RRG final en adoptant une formulation de fonction objectif intégrant des contraintes. Des a priori à la fois biologiques (sur les interactions entre les gènes) et structuraux (sur la connectivité des nœuds) ont été considérés pour restreindre l'espace des solutions possibles. Les différents a priori donnent des fonctions objectifs ayant des propriétés différentes, pour lesquelles des stratégies d'optimisation adaptées (continue et/ou discrète) peuvent être appliquées. Les post-traitement que nous avons développé ont mené à un ensemble de méthodes nommés BRANE, pour "Biologically-Related A priori for Network Enhancement". Pour chacune des méthodes développées (BRANE Cut, BRANE Relax et BRANE Clust), nos contributions sont triples : formulation de la fonction objectif à l'aide d'a priori, développement de la stratégie d'optimisation et validation (numérique et biologique) sur des données de parangonnage issues des challenges DREAM4 et DREAM5, montrant ainsi des améliorations pouvant atteindre 20%.En complément de l'inférence de réseaux, notre travail s'est étendu à des traitements de données sur graphe plus génériques, tels que les problèmes inverses. Nous avons notamment étudié HOGMep, une approche Bayésienne utilisant des stratégies d'approximation Bayésienne variationnelle. Cette méthode a été développée pour résoudre de façon conjointe, des problèmes de restauration et de classification sur des données multi-composantes (signaux et images). Les performances d'HOGMep dans un contexte de déconvolution d'image couleur montrent de bonnes qualités de reconstruction et de segmentation. Une étude préliminaire dans un contexte de classification de données médicales liant génotype et phénotype a également montré des résultats prometteurs pour des adaptions à venir en bioinformatiques. / The discovery of novel gene regulatory processes improves the understanding of cell phenotypicresponses to external stimuli for many biological applications, such as medicine, environmentor biotechnologies. To this purpose, transcriptomic data are generated and analyzed from mi-croarrays or more recently RNAseq experiments. For each gene of a studied organism placed indifferent living conditions, they consist in a sequence of genetic expression levels. From thesedata, gene regulation mechanisms can be recovered by revealing topological links encoded ingeometric graphs. In regulatory graphs, nodes correspond to genes. A link between two nodesis identified if a regulation relationship exists between the two corresponding genes. Such net-works are called Gene Regulatory Networks (GRNs). Their construction as well as their analysisremain challenging despite the large number of available inference methods.In this thesis, we propose to address this network inference problem with recently developedtechniques pertaining to graph optimization. Given all the pairwise gene regulation informa-tion available, we propose to determine the presence of edges in the final GRN by adoptingan energy optimization formulation integrating additional constraints. Either biological (infor-mation about gene interactions) or structural (information about node connectivity) a priorihave been considered to reduce the space of possible solutions. Different priors lead to differentproperties of the global cost function, for which various optimization strategies can be applied.The post-processing network refinements we proposed led to a software suite named BRANE for“Biologically-Related A priori for Network Enhancement”. For each of the proposed methodsBRANE Cut, BRANE Relax and BRANE Clust, our contributions are threefold: a priori-based for-mulation, design of the optimization strategy and validation (numerical and/or biological) onbenchmark datasets.In a ramification of this thesis, we slide from graph inference to more generic data processingsuch as inverse problems. We notably invest in HOGMep, a Bayesian-based approach using aVariation Bayesian Approximation framework for its resolution. This approach allows to jointlyperform reconstruction and clustering/segmentation tasks on multi-component data (for instancesignals or images). Its performance in a color image deconvolution context demonstrates bothquality of reconstruction and segmentation. A preliminary study in a medical data classificationcontext linking genotype and phenotype yields promising results for forthcoming bioinformaticsadaptations.

Le domaine scientifique de la Biologie des Systèmes étudie les interactions entre les composantes d'un système biologique afin d'en comprendre son fonctionnement global. Au cours de cette these, nous avons d'abord utilisé des graphes simples. Cette approche a permis d' appréhender la manière dont un réseau biologique peut interagir avec son environnement, lui-même modélisé par un autre réseau. Nous avons ensuite défini le formalisme MIB (Model of Interactions in Biology) qui permet de définir, rechercher et étudier les motifs hétérogènes. Enfin pour approfondir l'étude de la structure et de la dynamique, nous avons proposé le formalisme MIN. MIN possède la structure bipartie de MIB, mais permet d'avoir des annotations beaucoup plus riches des noeuds et des arcs du réseau qui peuvent être utilisées pour la traduction des données automatiquement en d'autres formalismes couramment utilisés en modélisation biologique, tels que les équations différentielles ou la modélisation logique.

La biologie des systèmes s’est beaucoup développée ces dix dernières années, confrontant plusieurs niveaux biologiques (molécule, réseau, tissu, organisme, écosystème…). Du point de vue de l’étude de l’évolution, elle offre de nombreuses possibilités. Cette thèse porte sur le développement de nouvelles méthodologies et de nouveaux outils pour étudier l’évolution des systèmes biologiques tout en considérant l’aspect multidimensionnel des données biologiques. Ce travail tente de palier un manque méthodologique évidant pour réaliser des études haut-débit dans le récent domaine de la biologie évolutionnaire des systèmes. De nouveaux messages évolutifs liés aux contraintes intra et inter processus ont été décrites. En particulier, mon travail a permis (i) la création d’un algorithme et un outil bioinformatique dédié à l’étude des relations évolutives d’orthologie existant entre les gènes de centaines d’espèces, (ii) le développement d’un formalisme original pour l’intégration de variables biologiques multidimensionnelles permettant la représentation synthétique de l’ histoire évolutive d’un gène donné, (iii) le couplage de cet outil intégratif avec des approches mathématiques d’extraction de connaissances pour étudier les perturbations évolutives existant au sein des processus biologiques humains actuellement documentés (voies métaboliques, voies de signalisations…). / Systems biology has developed enormously over the 10 last years, with studies covering diverse biological levels (molecule, network, tissue, organism, ecology…). From an evolutionary point of view, systems biology provides unequalled opportunities. This thesis describes new methodologies and tools to study the evolution of biological systems, taking into account the multidimensional properties of biological parameters associated with multiple levels. Thus it addresses the clear need for novel methodologies specifically adapted to high-throughput evolutionary systems biology studies. By taking account the multi-level aspects of biological systems, this work highlight new evolutionary trends associated with both intra and inter-process constraints. In particular, this thesis includes (i) the development of an algorithm and a bioinformatics tool dedicated to comprehensive orthology inference and analysis for hundreds of species, (ii) the development of an original formalism for the integration of multi-scale variables allowing the synthetic representation of the evolutionary history of a given gene, (iii) the combination of this integrative tool with mathematical knowledge discovery approaches in order to highlight evolutionary perturbations in documented human biological systems (metabolic and signalling pathways...).

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

Le travail présenté s'articule autour de l'étude in silico des réseaux biologiques en abordant aussi bien les aspects d'intégration, de formalisation et de modélisation des réseaux et sous-réseaux biologiques. Dans ce contexte, les travaux ont porté dans un premier temps, sur le développement d'un outil d'intégration Cyclone à même d'assurer un accès et une exploitation simplifiés des données présentes dans la base de données BioCyc puis, dans un second temps, sur le développement d'un cadre de modélisation des graphes particulièrement adapté à l'étude de réseaux d'interactions hétérogènes, MIB (pour Modèle d'Interaction Biologique). Enfin, ces développements ont été mis à profit afin d'une part, de caractériser et d'étudier la présence et le mode de connexion de sous-réseaux ou motifs à l'intérieur de réseaux plus vastes et d'autre part, d'étudier et de modéliser la voie métabolique du galactose chez la levure Saccharomyces cerevisiae en tant que boucle de rétroaction impliquant régulation transcriptionnelle et interaction protéine-protéine.

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.

La biologie est un domaine scientifique qui reste encore très incomplet au sens où la somme de connaissances qu'il nous reste à découvrir est non négligeable. Il est fréquent que les techniques de laboratoire traditionnelles soient inadaptées à la complexité du problème traité. Une raison possible à cela est que leur mise en œuvre requiert souvent beaucoup de temps et/ou de moyens financiers. Par ailleurs, certaines d'entre elles produisent des résultats peu fiables ou à trop faible débit. C'est pourquoi ces techniques peinent parfois à apporter des réponses aux nombreuses questions biologiques non résolues. En parallèle, l'évolution des biotechnologies a permis de produire massivement des données biologiques. Les expériences biologiques à haut débit permettent à présent de caractériser des cellules à l'échelle du génome et sont porteuses d'espoir pour la compréhension de phénomènes biologiques complexes. Ces deux faits combinés ont induit un besoin croissant de mathématiciens et de statisticiens en biologie. La tâche des bioinformaticiens est non seulement d'analyzer efficacement les masses de données produites par les expériences à haut débit et d'en extraire une information fiable mais aussi d'élaborer des modèles de systèmes biologiques menant à des prédictions utiles. L'inférence de réseaux de régulation et la recherche de gènes de maladie sont deux exemples parmi d'autres, de problèmes où une expertise bioinformatique peut s'avérer nécessaire. L'inférence de réseaux de régulation consiste à identifier les relations de régulation transcriptionnelle entre des gènes régulateurs appelés facteurs de transcription et des gènes cibles. Par ailleurs, la recherche de gènes de maladie consiste à déterminer les gènes dont les mutations mènent au développement d'une maladie génétiquement transmise. Dans les deux cas, les biologistes sont confrontés à des listes de milliers de gènes à tester. Le défi du bioinformaticien est donc de produire une liste de priorité où les interactions ou gènes candidats sont rangés par ordre de pertinence au problème traité, en vue d'une validation expérimentale. Les deux problèmes mentionnés plus haut partagent une caractéristique commune : ce sont tous les deux des problèmes de priorisation pour lesquels un petit nombre d'exemples positifs est disponible (des interactions connues ou gènes de maladie déjà identifiés) mais pour lesquels on ne dispose pas de données négatives. En effet, les bases de données biologiques ne reportent que rarement les paires de gènes non interactives. De même, il est difficile voire impossible de déterminer à coup sûr qu'un gène n'est pas impliqué dans le développement d'une maladie. Par ailleurs, des nombreux exemples indéterminés existent qui sont par exemple des gènes dont on ne sait pas si ils interagissent avec un facteur de transcription ou encore des gènes dont on ne sait pas s'ils sont causaux pour une maladie. Le problème de l'apprentissage à partir d'exemples positifs et indéterminés (PU learning en anglais) a été étudié en soi dans le domaine de l'apprentissage automatique (machine learning). L'objet de cette thèse est l'étude de méthodes de PU learning et leur application à des problèmes biologiques. Le premier chapitre présente le bagging SVM, un nouvel algorithme de PU learning et évalue ses performances et propriétés sur un jeu de données standard. L'idée principale de cet algorithme est d'exploiter au moyen d'une procédure voisine du bagging, une caractéristique intrinsèque d'un problème de PU learning qui est que l'ensemble des exemples indéterminés contient des positifs cachés. Le bagging SVM atteint des performances comparables à l'état de l'art tout en faisant preuve de bonnes propriétés en termes de rapidité et d'échelle par rapport au nombre d'exemples. Le deuxième chapitre est consacré à SIRENE, une nouvelle méthode supervisée pour l'inférence de réseaux de régulation. SIRENE est un algorithme conceptuellement simple qui donne de bons résultats en comparaison à des méthodes existantes pour l'inférence de réseaux. Enfin, le troisième chapitre décrit ProDiGe, un algorithme pour la priorisation de gènes de maladie à partir d'exemples positifs et indéterminés. Cet algorithme, issu du bagging SVM, peut gérer la recherche de gènes de maladies à l'échelle du génome et permet d'intégrer plusieurs sources de données. Sa capacité à retrouver correctement des gènes de maladie a été démontrée sur un jeu de données réel.