Petri nets are a simple formalism for modelling concurrent computation. This formalism has been proposed as a promising tool to describe and analyse biochemical networks. In this thesis, we explore the structural properties of Petri nets as a mean to provide information about the biochemical system evolution and its dynamics, especially when kinetic data are missing, making simulations impossible. In particular, we consider the structural properties of siphons and traps. We show that these structures entail a family of particular stability properties which can be characterized by a fragment of CTL over infinite state structures. Mixed integer linear programs have been proposed and a state-of-the-art algorithm from the Petri net community has been described later to compute minimal sets of siphons and traps in Petri nets. We present a simple boolean model capturing these notions and compare SAT and CLP methods for enumerating the set of all minimal siphons and traps of a Petri net. Our methods are applied to a benchmark composed of the 403 models from the biomodels.net repository. We analyse why these programs perform so well on even very large biological models. We show that, in networks with bounded tree-width, the existence of a minimal siphon containing a given set of places can be decided in a linear time, and the Siphon-Trap property as well. Moreover, we consider two other Petri net structural properties: place and transition invariants. We present a simple method to extract minimal semi-positive invariants of a Petri net as a constraint satisfaction problem on finite domains using constraint programming with symmetry detection and breaking. This allows us to generalize well-known results about the steady-state analysis of symbolic Ordinary Differential Equations systems corresponding to biochemical reactions by taking into account the structure of the reaction network. The study of the underlying Petri net, initially introduced for metabolic flux analysis, provides classes of reaction systems for which the symbolic computation of steady states is possible.

The aim of this habilitation is to exhibit my contributions in several area of Bio-Algorithmics. Rather than an exhaustive presentation of my works, I have made the choice of presenting results we obtained with collaborators on a representative subset of the problems I have been involved in since 2005. For ease of readability, I will regroup the results obtained according to the biological problems: i) RNA structures comparison, ii) Genomes comparison and iii) Pattern matching in biological networks and their respective combinatorial objects: i) Arc-annotated sequences, ii) Permutations and Sequences and iii) Graphs. More precisely, The first part will be devoted to the Arc-Annotated Sequences that are used in RNA structure comparison. We will focus on five problems that we investigated: LAPCS, APS, MAPCS, EDIT and ALIGN. In the second part, we will consider the two main research area related to comparative genomics we were involved in: gene clusters detection and (dis)similarity measures computation -- which rely on permutation and string representations. Finally, we will present some results that were obtained mainly during the PhD of Florian Sikora that I co-supervised.

La variabilité des vitesses d'évolution entre sites est un phénomène très répandu au sein des séquences génétiques. Celui-ci est généralement modélisé par une loi gamma dont le paramètre de forme doit être estimé. Nous proposons ici une méthode visant à déterminer la valeur efficace de ce paramètre, c'est-à-dire la valeur la plus adaptée à l'estimation de topologies d'arbres. Nous montrons que (1)les valeurs efficaces conduisent généralement à sous-estimer la variabilité des vitesses et (2), celles-ci offrent une amélioration significative en termes de précision topologique comparé aux cas ou l'inférence d'arbre est réalisée à partir des vraies valeurs (inconnues) du paramètre. Outre la paramétrisation adéquate des modèles de substitution, l'exploration de l'espace des topologies d'arbres est un point sensible pour bon nombre de méthodes d'inférences de phylogénies. Nous proposons ici une nouvelle méthode pour l'estimation d'arbres de vraisemblances maximales, basée sur la modification simultanée de la topologie de l'arbre et de ses longueurs de branches. Nous montrons que cette approche autorise la construction de topologies particulièrement fiables à partir de l'analyse de plusieurs centaines de séquences.

Un embryon, initialement composé de cellules identiques, se transforme progressivement en une structure spatialement organisée de tissus distincts aux frontières clairement démarquées. Ce processus de formation de motifs est étudié dans le domaine de la biologie du développement. Les interactions cellulaires jouent un rôle clé dans la formation de motifs, et l'effet de communauté est un exemple d'une telle interaction. Une population de cellules dans un embryon présente un effet de communauté quand elle forme une communauté de cellules ayant une identité commune obtenue grâce à l'échange de molécules de signalisation qui diffusent dans le milieu (i.e. des morphogènes). Cet effet permet aux cellules de la communauté de maintenir un profil d'expression génétique commun pendant une période prolongée, et pour se différencier finalement de manière coordonnée dans un tissu fonctionnel, comme le muscle. Les processus auto-organisés tels que l'effet de communauté sont difficiles à comprendre intuitivement. Une description satisfaisante peut être obtenue sous la forme d'un modèle formel. Quelques modèles computationnels des effets de la communauté ont été donnés dans la littérature. Cependant, la notion d'espace n'ayant pas été explicitement incluse dans ces modèles, il est difficile de comprendre comment l'effet de communauté participe à la formation de motifs. Dans ce travail, nous étudions le comportement de l'effet de communauté dans l'espace et étudions ses rôles dans d'autres processus de formation de motif, en utilisant la modélisation computationnelle. Les contributions principales de cette thèse sont les suivantes: * Une méthode de réduction de modèle est développée pour l'analyse stochastique. Par cette méthode nous avons pu démontrer que le modèle de l'effet de communauté dans Xenopus est influencé par un bruit stochastique. * En utilisant un modèle spatial simple d'effet de communauté, nous montrons que celui-ci doit finalement se propager dans l'ensemble de la population de cellules qui réagissent au morphogène. Cela est confirmé par un modèle plus détaillé. * Deux modèles montrant comment cette expansion peut être contrôlée sont présentés. Tout d'abord, si l'effet de communauté est augmenté d'un mécanisme de rétroaction négative, il forme un système de réaction-diffusion qui s'auto-organise et forme une zone d'activation stable et localisée. En second lieu, quand un circuit simple de repression génétique est associé au circuit produisant l'effet de communauté, un motif d'expression de gène avec une frontière bien démarquée apparaît en réponse à un gradient de morphogène transitoire. Le motif reste stable y compris après disparition du gradient, ce qui indique que le réseau de gènes garde en mémoire la dynamique du morphogène.

Les modèles de Markov cachés (MMC) - par exemple ceux de la librairie Pfam - sont des outils très populaires pour l'annotation des domaines protéiques. Cependaqnt, ils ne sont pas toujours adaptés aux protéines les plus divergentes. C'est notamment le cas avec Plasmodium falciparum (principal agent du paludisme chez l'Homme), où les MMC de Pfam identifient peu de familles distinctes de domaines, et couvrent moins de 50% des protéines de l'organisme. L'objectif de cette thèse est d'apporter des méthodes nouvelles pour affiner la détection de domaines dans les protéines divergentes. Le premier axe développé est une approche d'identification de domaines utilisant leurs propriétés de co- occurrence. Différentes études ont montré que la majorité des domaines apparaissent dans les protéines avec un ensemble très réduits d'autres domaines favoris. Notre méthode exploite cette propriété pour détecter des domaines trop divergents pour être identifiés par l'approche classique. Cette détection s'accompagne d'une estimation du taux d'erreur par une procédure de ré-échantillonnage. Chez P. falciparum, elle permet d'identifier, avec un taux d'erreur estimé inférieur à 20%, 585 nouveaux domaines - dont 159 familles étaient inédites dans cet organisme -, ce qui représente 16% du nombre de domaines connus. Le second axe de mes recherches présente plusieurs méthodes de corrections statistiques et évolutives des MMC pour l'annotation d'organismes divergents. Deux types d'approches ont été proposées. D'un côté, nous intégrons aux alignements d'apprentissage des MMC les séquences précédemment identifiés dans l'organisme cible ou ses proches relatifs. La limitation de cette solution est que seules des familles de domaines déjà connues dans le taxon peuvent ainsi être identifiées. Le deuxième type d'approches contourne cette limitation en corrigeant tous les modèles par une prise en compte de l'évolution des séquences d'apprentissage. Pour cela, nous faisons appel à des techniques classiques de la bioinformatique et de l'apprentissage statistique. Les résultats obtenus offrent un ensemble de prédictions complémentaires totalisant 663 nouveaux domaines supplémentaires - dont 504 familles inédites -, soit une augmentation de 18% à ajouter aux précédents résultats.

A l'heure de l'acquisition de données à haut débit concernant le métabolisme cellulaire et son évolution, il est absolument nécessaire de disposer de modèles permettant d'intégrer ces données en un ensemble cohérent, d'en interpréter les variations métaboliques révélatrice, les étapes clefs où peuvent s'exercer des régulations, voire même d'en révéler des contradictions apparentes mettant en cause les bases sur lesquelles le modèle lui-même est construit. C'est ce type de travail que j'ai entrepris à propos de données expérimentales obtenues dans le laboratoire biologique sur le métabolisme de cellules tumorales en réponse à un traitement anti-cancéreux. Je me suis attachée à la modélisation d'un point particulier de ce métabolisme. Il concerne le métabolisme des glycérophospholipides qui sont de bons marqueurs de la prolifération cellulaire. Les phospholipides constituent l'essentiel des membranes d'une cellule et l'étude de leur synthèse (en particulier chez les cellules de mammifères) est de ce fait un sujet important. Ici, nous avons pris le parti de mettre en place un modèle mathématique par équations différentielles ordinaires, qui est essentiellement basé sur des équations hyperboliques (Michaelis-Menten), mais aussi sur des cinétiques type loi d'action de masse et diffusion. Le modèle, composé de 8 équations différentielles, donc de 8 substrats d'intérêt, comporte naturellement des paramètres inconnus in vivo, et certains dépendents des conditions cellulaires (différentiations de cellules, pathologies, . . .). Le modèle sépare la structure du réseau métabolique, l' ́écriture de la matrice de stoechiométrie, celles des équations de vitesse et enfin des équations différentielles. Le modèle choisi est le modèle murin (souris/rat), parce qu'il est lui-même un modèle de l'homme. Plusieurs conditions sont successivement considérées pour l'identification des paramètres, afin d'étudier les liens entre la synthèse de phospholipides et le cancer : - le foie sain du rat, - le mélanome B16 et le carcinome de la lign ́ee 3LL chez la souris, respectivement sans traitement, en cours de traitement 'a la Chloroéthyl-nitrosourée et après traitement, - enfin le mélanome B16 chez la souris sous stress de privation de méthionine. En résumé, ce travail fourni une interprétation nouvelle des données expérimentales en montrant le rôle essentiel de la PEMT et la nature superstable de l'état sta- tionnaire de fonctionnement du réseau métabolique des phospholipides lors de la cancérogènèse et du traitement des cancers. Il montre bien l'avantage de l'utilisation d'un modèle mathématique dans l'interprétation de données métaboliques complexes.

In this thesis, we presented three main types of analyses of metabolism, most of which involved symbiosis: metabolic dialogue between a trypanosomatid and its symbiont, comparative analyses of metabolic networks and exploration of metabolomics data. All of them were essentially based on genomics data where metabolic capabilities were predicted from the annotated genes of the target organism, and were further refined with other types of data depending on the aim and scope of each investigation. The metabolic dialogue between a trypanosomatid and its symbiont was explored with functional and evolutionary goals which included analysing the classically defined pathways for the synthesis of essential amino acids and vitamins, exploring the genome-scale metabolic networks and searching for potential horizontal gene transfers from bacteria to the trypanosomatids. The comparative analyses performed focused on the common metabolic capabilities of different lifestyle groups of bacteria and we proposed a method to automatically establish the common and the group-specific activities. The application of our method on metabolic stories enumeration to the yeast response to cadmium exposure was a validation of this approach on a well-studied biological response to stress. We showed that the method captured well the underlying knowledge as it extracted stories allowing for further interpretations of the metabolomics data mapped into the genome-scale metabolic model of yeast

La métagénomique vise à étudier le contenu génétique et génomique d'un échantillon provenant d'un environnement naturel. Cette discipline récente s'attache à étudier les génomes de différents organismes provenant d'un même milieu. La métagénomique pose de nouvelles questions, tant d'un point de vue biologique qu'informatique. Les masses de données générées par les études métagénomiques et la complexité des milieux étudiés nécessitent de développer de nouvelles structures de données et de nouveaux algorithmes dédiés. Parmi les différentes approches existantes en métagénomique, la métagénomique comparative consiste à comparer plusieurs métagénomes afin d'en connaitre les divers degrés de similarité. Lorsque cette comparaison se base uniquement sur le contenu brut des échantillons, sans faire appel à des connaissances externes, on parle de métagénomique comparative de novo. L'objectif des travaux que nous proposons est de développer une méthode permettant d'extraire les séquences similaires entre deux jeux de données métagénomiques, où chaque jeu peut être composé de centaines de millions de courtes séquences d'adn. La comparaison proposée consiste à identifier les séquences d'un premier jeu similaires à au moins une séquence d'un second jeu. Afin d'être rapide et économe en mémoire, l'implémentation de notre méthode a nécessité la conception d'une nouvelle structure d'indexation, basée sur le filtre de bloom. Le logiciel final, nommé Compareads, a une consommation mémoire faible (de l'ordre de quelques go) et peut calculer l'intersection de deux échantillons de 100 millions de séquences chacun en une dizaine d'heures. Notre méthode est une heuristique qui génère un faible taux de faux positifs. Le logiciel Compareads est dédié à l'analyse de grands jeux de données métagénomiques. À l'heure actuelle, il est le seul outil capable de comparer de tels jeux. Compareads a été appliqué sur plusieurs projets métagénomiques. Notre outil produit des résultats robustes, biologiquement exploitables et en accord avec diverses méthodes fondamentalement différentes. Il est actuellement utilisé de manière intensive sur les échantillons provenant de l'expédition tara oceans. Sur ce projet, notre méthode a permis de mettre en évidence que les grands systèmes océaniques influent sur la répartition globale des microorganismes marins.

Les cytochromes P450 (CYP450) sont des hémoprotéines intervenant généralement dans la détoxication de l’organisme sous forme de biodégradation de molécules xénobiotiques et participent à la décomposition de certains médicaments. Cependant, les gènes codant pour les protéines CYP450 sont souvent sous-analysés dans les études génomiques à grande échelle en raison de leur difficulté d’analyse due à un haut taux de polymorphisme. Deux sous-familles seront étudiées plus en profondeur: les sous-familles CYP3A et CYP4F. La sous-famille CYP3A métabolise environ 50% des médicaments alors que les enzymes CYP4F, quant à eux, sont impliquées dans le métabolisme de composés endogènes, de nutriments et de médicaments. Les gènes de ces sous-familles sont fortement polymorphes et ce, à travers les populations humaines. Ainsi, la variabilité entre les différentes populations peut affecter la réponse aux médicaments et autres fonctions métaboliques. Dans ce projet, deux grands jeux de données, l’un en génétique des populations (le Projet des 1000 Génomes) et l’autre en transcriptomique (GTEx) seront utilisés afin d’identifier des signatures de sélection naturelle dans les gènes CYP3A et CYP4F, ainsi que leur impact sur l’expression génique de ces gènes. Nous avons détecté différentes forces de sélection (positive et balancée) dans les deux sous-familles. Certains polymorphismes identifiés comme étant sous pression sélective sont associés à une expression différentielle des gènes des deux sous-familles. Ce projet permet de mieux comprendre l’impact des mutations sous pression sélective se situant dans les gènes des sous-familles CYP3A et CYP4F. Cette caractérisation génétique permettra d’obtenir des prédictions plus fiables en pharmacogénomique et en génomique humaine, en raison de l’influence de ces gènes sur la réponse aux médicaments. / Cytochromes P450 (CYP450) are hemoproteins generally involved in the detoxification of the body of xenobiotic molecules and participate in the metabolism of many drugs. Genetic polymorphisms have been found to impact drugs responses and metabolic functions. However, genes encoding CYP450 proteins are often under-analyzed in large-scale genomic studies because the difficulty of analysis due to of their high rate of polymorphism. In this study, we investigate the genetic diversity for CYP450 genes. We found that two clusters, CYP3A and CYP4F, are notably differentiated across human populations with evidence for selective pressures acting on both clusters. The CYP3A subfamily metabolizes approximately 50\% of drugs while CYP4F enzymes are involved in the metabolism of endogenous compounds, nutrients and drugs. Indeed, we found signals of recent positive selection in CYP3A and CYP4F genes and signals of balancing selection in CYP4F genes. Futhermore, unusual linkage disequilibrium is detected in both cluster, suggesting co-evolution. eQTLs were also found in both clusters which indicate co-regulation and epistasis.

Résumé : INTRODUCTION : Les protéines doivent se retrouver dans le bon compartiment cellulaire afin de pouvoir exercer leurs fonctions. Une fois synthétisées dans le cytoplasme, les protéines se déplacent à travers les différents compartiments cellulaires, guidés par des signaux de ciblage protéique. Des modifications post-traductionnelles jouent un rôle dans la régulation et le contrôle dynamique de la localisation des protéines. Des exemples dans la littérature indiquent que cette régulation existe également au niveau pré-traductionnel. Ce projet cherche à investiguer cette régulation pré-traductionnelle sur les motifs d’import et d’export nucléaires choisi comme signaux modèles. A l’aide de la bio-informatique, nous caractérisons cette régulation pré-traductionnelle, pour ensuite analyser de façon quantitative le niveau du contrôle de l’inclusion de ces motifs dans les transcrits en considérant des données de RNA-seq. MÉTHODE : Des données du transcriptome humain ont été regroupées dans une base de données locale MySQL. Une curation extensive de bases de données publiques a permis d’identifier les motifs d’import et d’export nucléaires, validés expérimentalement. Des scripts dans les langages Python et PHP ont été créés afin d’interroger la base de données et d’implémenter les algorithmes. Par la suite des ensembles de données de RNA-seq ont été analysés pour quantifier le niveau d’inclusion de ces motifs. RÉSULTATS : La majorité de ces motifs varie pour les gènes dont seulement certaines isoformes contiennent ce motif. Nous avons pu déterminer la distribution de la position des motifs chez l’humain, et caractériser quatre différents types de régulation pré-traductionnelles pour ces motifs. Ces catégories sont : les sites d’initiation et de terminaison différentiels de transcription /traduction, l’épissage (d’introns/d’exons) et le décalage du cadre de lecture. L’index d’inclusion du motif (MII) varie pour les gènes à travers différents tissus d’un même ensemble de données et varie également dans des tissus cancéreux. Certains gènes produisent des isoformes dont le MII est tissu-spécifique. CONCLUSION : La régulation pré-traductionnelle de l’inclusion de motifs de ciblage d’import et d’export nucléaires joue un rôle important sur la localisation de la protéine résultante. Les données de RNA-seq ont abouti à une analyse quantitative sur ces motifs dans différents tissus normaux et cancéreux. / Abstract : INTRODUCTION: Proteins have to be in the right compartment in order to perform their functions. Once synthesized in the cytosol, proteins are guided by sorting signals as they move through different subcellular compartments. Post-translational modifications play a role in the regulation and dynamic control of protein localization. Some examples in the literature show that this regulation also exist at the pre-translational level. The purpose of this research is to investigate this regulation on nuclear import and export motifs, chosen as model signals. Using bioinformatics, we characterize this pre-translational regulation then using RNA-seq data, perform a quantitative analysis on the level of motif inclusion among transcripts. METHODS: Data of the human transcriptome was put in MySQL in house. For this study, we used experimental data. Extensive manual curation was performed on nuclear import and export motifs that were experimentally validated and obtained from public databases. In order to interrogate the database and implement the algorithms, scripts in Python and PHP were used. RNA-seq data were used and analyzed in order to quantify the level of inclusion of these motifs. RESULTS: The majority of these motifs are only present in a subset of the coding isoforms of the genes. The position distribution of these motifs in the human proteome was determined. We characterized four different types of pre-translational regulation for alternative motifs. The categories a re: differential initiation and termination sites of transcription/translation, splicing (of introns/exons) and frameshift mutation. Genes have a motif inclusion index (MII) that varies among different types of tissues within the same dataset and varies as well in cancer tissues. Some genes produce isoforms with MII that are tissue-specific. CONCLUSION: Pre-translational regulation plays an important role in the inclusion of nuclear import and export motifs and the localization of proteins containing them. Quantitative analyses showing the behaviour of the motifs in different types of normal and cancer tissues were performed with RNA-seq data.