Journées thématiques "Méthodes de réduction de modèles"

Thème de la réunion

La modélisation et l’étude des réseaux biomoléculaires est un domaine en pleine expansion, et les modèles considérés sont de taille et complexité croissantes. C’est pourquoi de plus en plus d’attention et d’efforts sont portés sur les techniques et méthodes de réduction de modèles. Le choix de la méthode de réduction va bien évidemment dépendre du formalisme de modélisation utilisé, du système biologique étudié, des données biologiques accessibles, etc... Un des critères fondamentaux dans le choix de la méthode de réduction est l’ensemble des propriétés dynamiques qui sont conservées : en particulier, les attracteurs, la fonctionnalité des circuits, les échelles de temps, et les comportements transitoires peuvent être impactés lors de la réduction du système, ce qui peut nuire à l’interprétation biologique des propriétés du systèmes. Cet atelier a pour but de faire le point sur les différentes approches utilisées dans le cadre de la réduction de modèles biologiques discrets. Ainsi, les participants pressentis ont des expériences d’étude et d’utilisation de méthodes de réductions dans divers types de réseaux biologiques (réseaux de régulation, réseaux métaboliques...), ayant recours à différents formalismes de modélisation (réseaux d’automates, réseaux booléens, modélisation à base de règles, réseaux d’interactions...). L’objectif sera de mieux comprendre les différentes approches existantes, les invariants conservés par ces approches, ainsi que les applications transversales possibles à différents formalismes.

Programme

Jeudi 28 mai 2015

10h15 - 10h30 - slides
    Anne Siegel - Présentation du GT Bioss
10h30 - 11h15 - slides
    Jérôme Feret - Réduction de modèles de voies de signalisation intracellulaires
11h15 - 12h00 - slides
    Ovidiu Radulescu - Taming the complexity of biochemical networks through model reduction and tropical geometry
14h00 - 14h45 - slides
    Adrien Richard - Reduction of finite dynamical systems and linear network coding solvability
14h45 - 15h30 - slides
    Damien Éveillard - Rechercher des modules dans les réseaux métaboliques
16h00 - 16h45 - slides
    Guillaume Madelaine - Structural simplification of chemical reaction networks preserving deterministic semantics
16h45 - 17h30 - slides
    Adrien Basso-Blandin - Modèle de représentation de connaissances annoté pour la biologie
17h30 - 18h15 - slides
    Loïc Paulevé - Goal-oriented reduction of automata networks

Vendredi 29 mai 2015

09h00 - 09h45 - slides
    François Fages - Réductions de modèles par épimorphismes de sous-graphes
09h45 - 10h30 - slides
    Franck Delaplace - Analogous dynamics of Boolean networks
11h00 - 11h45 - slides
    Aurélien Naldi - Une méthode de réduction pour la manipulation de grands modèles logiques
11h45 - 12h30 - slides
    Wassim Abou-Jaoudé - Derivation of dynamical qualitative models from biochemical networks
14h00 - 14h45 - slides
    Tarek Melliti - Analysis of modular organisation of interaction networks based on asymptotic dynamics
14h45 - 15h30 - slides
    Laurent Tournier - Uncovering regulations in B. subtilis metabolic network, combining optimal resource allocation and Boolean inference

Résumés

Wassim Abou-Jaoudé - Derivation of dynamical qualitative models from biochemical networks
As technological advances allow a better identification of cellular networks, more and more molecular data are produced allowing the construction of detailed molecular interaction maps. One strategy to get insights into the dynamical properties of such systems is to derive compact dynamical models from these maps, which would then be handled more efficiently for the analysis of their dynamics. Starting from two specific case studies of networks, I will present a methodology for the derivation of qualitative dynamical models from biochemical networks. Properties are formalised using abstraction interpretation techniques. We first abstract states and traces by quotienting the state space by intervals. The induced abstract semantics is too coarse to reproduce the properties of interest for our two examples. We then refine the abstract semantics by introducing additional constraints and information on the kinetics computed by abstract interpretation. The resulting semantics is able to reproduce our properties of interest.

Adrien Basso-Blandin - Modèle de représentation de connaissances annoté pour la biologie
L'étude des voies de signalisations biologiques des cancers est un travail extrêmement complexe. En effet, de tels systèmes possèdent de nombreux paramètres, agents et processus, mais ils sont étudiés par fragments et leurs littératures et données sont fragmentées, distribuées et parfois contradictoires. Il est difficile de construire les modèles complets, explicatifs de tels systèmes complexes et des interactions dans ces systèmes qui sont provoquées par beaucoup de facteurs interagissants de manière peu connue ou mal comprise. Les "Big mechanisms" sont de grands modèles explicatifs de systèmes complexes au sein desquels les interactions ont des effets causals importants. La collection de données de masse est de plus en plus automatisée, néanmoins, la création de "Big mechanisms" reste un processus manuel de plus en plus difficile à réaliser de par la fragmentation et la distribution de connaissances. L'automatisation de la conception de ces "Big mechanisms" permettrait une évolution majeure pour la science et la façon dont la recherche est réalisée. Ici nous introduisons d'un coté un modèle de représentation de connaissance pour la biologie afin d'intégrer plus ou moins immédiatement et automatiquement (ou "semi automatiquement") au sein de modèles causals explicatifs, des connaissances biologiques extraites de la littérature. Combiné à ce modèle, nous proposons une traduction automatique de cette représentation de connaissances en modèles Kappa.

Franck Delaplace - Analogous dynamics of Boolean networks
Different Boolean networks may reveal similar dynamics although their definition differs, then preventing their distinction from the observations. This raises the question about the sufficiency of a particular Boolean network for properly reproducing a modeled phenomenon to make realistic predictions. The question actually depends on the invariant properties of behaviorally similar Boolean networks. We address this issue by considering that the similarity is formalized by isomorphism on graphs modeling their dynamics. The similarity also depends on the  parameter governing the updating policy, called the "mode". We define a general characterization of the group of isomorphism preserving the mode. From this characterization, we deduce invariant structural properties of the interaction graph and conditions to maintain an equivalence through mode variation.

Damien Éveillard - Rechercher des modules dans les réseaux métaboliques
Les récents progrès biotechnologiques permettent de reconstruire des réseaux métaboliques à l’échelle des génomes pour notamment appliquer les approches de type FBA. Cependant, au delà de l’intérêt de ces approches pour prédire des comportements quantitatifs, l’analyse per se des réseaux métaboliques reste difficile. Cette difficulté est particulièrement d’actualité pour analyser le réseau métabolique qui résultent d’interactions microbiennes, et qui mettent en oeuvre différents réseaux métaboliques issus des espèces bactériennes en présence. Cet exposé propose de surmonter cette difficulté avec la recherche des modules de flux. Cette technique analyse le réseau métabolique en décomposant l’espace de solutions optimales. Nous montrerons, après application sur deux systèmes de référence, que cette décomposition est biologiquement intéressante biologique et qu’elle ouvre de riches perspectives méthodologiques pour la modélisation des réseaux métaboliques.

François Fages - Réductions de modèles par épimorphismes de sous-graphes
Nous proposons un cadre de réduction de modèles, basé uniquement sur des graphes, qui permet d'organiser les bases de modèles en un ordre partiel. Pour capturer le processus de réduction lui-même, nous utilisons un type particulier de morphismes de graphes: les épimorphismes de sous-graphes, qui permettent la fusion et l'effacement de sommets. Nous commencerons en analysant l'ordre partiel qui émerge des opérations de fusion et d'effacement, montrerons sa complexité théorique et sa résolution pratique en programmation par contraintes, et évaluerons les performances et la précision de cette approche sur la base de modèles BioModels. Enfin, nous discuterons de nos travaux en cours sur la recherche de motifs dans les réseaux de réactions protéiques, ainsi que sur la prise en compte des critères dynamiques par des méthodes d'algèbre tropicale.

Jérôme Feret - Réduction de modèles de voies de signalisation intracellulaire
Les voies de signalisation intracellulaire sont des cascades d'interaction entre protéines, qui permettent à la cellule de recevoir des signaux, de les propager jusqu'à son noyau, puis de les intégrer, ce qui, in fine, influe sur le comportement global de la cellule. Les protéines s'associent entre elles sur des sites de liaisons, puis modifient la structure spatiale de leurs voisines, ce qui a pour effet de cacher ou de découvrir leurs autres sites de liaisons, et donc d'empêcher ou de faciliter d'autres interactions. De vastes bases de données ont été conçues pour répertorier les différentes interactions connues entre les sites des protéines. Cependant, nous ne savons toujours pas clairement comment les propriétés physiologiques de la cellule émergent de ces interactions. La difficulté principale est la grande combinatoire de ces modèles. En effet, chaque protéine a beaucoup de sites de liaisons. Ainsi, un très grand nombre de complexes biomoléculaires différents peut se former. Pour décrire ces modèles, nous proposons d'utiliser des graphes pour la représentation des complexes biomoléculaires et des règles de réécritures pour la spécification des interactions entre les protéines. En particulier, ces règles sont contextuelles : elles décrivent non seulement les transformations sur les complexes biomoléculaires, mais aussi les conditions nécessaires à ces transformations. Ceci offre une représentation très compacte et pratique d'un modèle. Par ailleurs ces règles permettent de formaliser le comportement des modèles à différents niveaux d'abstraction (qualitatifs ou quantitatifs). Malheureusement, l'écueil de la complexité combinatoire refait surface lorsque l'on cherche à calculer de manière effective ce comportement.
Nous proposons une méthode pour réduire la taille des systèmes différentiels qui décrivent le comportement de ces modèles. Nous utilisons une analyse du flot d'information entre les différents sites des complexes biomoléculaires. Ainsi, pour chaque site de liaison d'un complexe biomoléculaire, nous détectons quelles sont les parties de ce complexe qui peuvent influencer la capacité de lier ou de délier ce site. Nous en déduisons des paires de sites dont on peut abstraire la relation entre l'état de liaison, car les ensembles de sites qu'ils peuvent influencer sont disjoints. Cela nous permet de découper les espèces biomoléculaires en plus petits morceaux (en séparant de telles paires de sites). Nous obtenons ainsi un système différentiel portant sur la concentration de ces morceaux de complexes biomoléculaires, qui sont beaucoup moins nombreux que les complexes biomoléculaires du système différentiel du modèle initial, et ce sans jamais avoir écrit explicitement ce système initial. Pourtant, notre méthode de réduction est exacte : nous avons la preuve que la solution du système obtenu, est la projection exacte de la solution du système initial.

Guillaume Madelaine - Structural simplification of chemical reaction networks preserving deterministic semantics
We study the structural simplification of chemical reaction networks preserving the deterministic kinetics. We aim at finding simplification rules that can eliminate intermediate molecules while preserving the dynamics of all others. The rules should be valid even though the network is plugged into a bigger context. An example is Michaelis-Menten’s simplification rule for enzymatic reactions. In this paper, we present a large class of structural simplifications rules for reaction networks that can eliminate intermediate molecules at equilibrium, without assuming that all molecules are at equilibrium, i.e. in a steady state. We prove the correctness of our simplification rules for all contexts that preserve the equilibrium of the eliminated molecule. Finally, we illustrate at a concrete example networks from systems biology, that our simplification rules may allow to drastically reduce the size of reaction networks in practice.

Tarek Melliti - Analysis of modular organisation of interaction networks based on asymptotic dynamics
We will present a work related to modularity in biological interaction networks, for which has been developped a discrete theoretical framework based on the analysis of the asymptotic dynamics of biological interaction networks. More precisely, we will exhibit formal conditions under which agents of interaction networks can be grouped into modules, forming a modular organisation. We will see that the conventional decomposition into strongly connected components fulfills the formal conditions of being a modular organisation. We will also propose a modular and incremental algorithm for an efficient equilibria computation. Furthermore, we will point out that our framework enables a finer analysis providing a decomposition into elementary modules, possibly smaller than strongly connected components.

Aurélien Naldi - Une méthode de réduction pour la manipulation de grands modèles logiques
Nous avons proposé une méthode de réduction de modèles logiques basée sur l'élimination de composants (sélectionnés manuellement) en réécrivant les fonctions logiques de leurs cibles. L'impact de cette réduction sur le comportement dynamique dans le cadre asynchrone est bien défini, en particulier elle conserve les attracteurs du système complet, mais peut dans certaines conditions en créer de nouveaux ou affecter leur atteignabilité. Après avoir introduit la méthode, je discuterai de critères de sélection des composants à éliminer afin de mieux préserver la dynamique, ainsi que de liens entre cette méthode de réduction et d'autres approches d'analyse statique.

Loïc Paulevé - Goal-oriented reduction of automata networks
I'll present on-going results on the reduction of automata networks dedicated to a given reachability goal (e.g., activation of a particular component). Based on previous work on abstract interpretation of traces in automata networks, I'll show that we can identify transitions that are useless for reaching a given goal state. At the end, the reduction produces an automata network that can generate all the minimal traces leading to the given goal, while significantly shrinking its global dynamics.

Ovidiu Radulescu - Taming the complexity of biochemical networks through model reduction and tropical geometry
Biochemical networks are used as models of cellular physiology with diverse applications in biology and medicine. In the absence of objective criteria to detect essential features and prune secondary details, networks generated from data are too big and therefore out of the applicability of many mathematical tools for studying their dynamics and behavior under perturbations. However, under circumstances that we can generically denote by multi-scaleness, large biochemical networks can be approximated by smaller and simpler networks. Model reduction is a way to find these simpler models that can be more easily analyzed. We discuss several model reduction methods for biochemical networks with polynomial or rational rate functions and propose as their common denominator the notion of tropical equilibration, meaning finite intersection of tropical varieties in algebraic geometry. Using tropical methods, one can strongly reduce the number of variables and parameters of biochemical network. For multi-scale networks, these reductions are computed symbolically on orders of magnitudes of parameters and variables, and are valid in wide domains of parameter and phase spaces.

Adrien Richard - Reduction of finite dynamical systems and linear network coding solvability
Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations towards their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. This problem can be formulated in terms of fixed points finite dynamical systems, which are usually called discrete networks, or Boolean networks when all the variables are binary variables.
Naldi, Remy, Thieffry and Chaouiya (TCS 2011) introduced technics for removing some variables in a finite dynamical system without changing the number of fixed points. In this presentation, we show that this reduction technics can be used to obtain new results on the linear network coding solvability problem.
We first show that triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing (this is the first classification result for the linear network coding solvability problem). Then, we exhibit a new class of non-linearly solvable graphs. Finally, we determine large classes of strictly linearly solvable graphs.

Laurent Tournier - Uncovering regulations in B. subtilis metabolic network, combining optimal resource allocation and Boolean inference
We previously developed and validated the constraint-based modeling method "Resource Balance Analysis" (RBA) that accurately predicts resource allocation (i.e. growth rate, protein allocation, metabolic configuration) in the model bacterium Bacillus subtilis for a wide range of growth conditions. RBA is able to predict induced/repressed subsystems in the metabolic network, thus mimicking the repression/activation of metabolic pathways by a genetic regulator. The question is now to explore systematically the relation between predicted metabolic configurations and simulated medium composition: (a) to determine a rule of activation of the encoding gene and (b) to determine if the inferred rule coincides with the known biological regulation of the gene. To explore the exponential number of predicted metabolic configurations, we propose to use Boolean inference. In particular, we propose a method to infer monotone (unate) Boolean functions on a minimal support. Applied to the central carbon metabolism of B. subtilis, first results are encouraging as the method predicts most of the regulations as they are known today.

Participants

Wassim ABOU-JAOUDE, Antique, ÉNS
Adrien BASSO-BLANDIN, LIP, ÉNS-Lyon
Franck DELAPLACE, IBISC, Université d'Évry - Val d'Essonne
Damien ÉVEILLARD, LINA, Université de Nantes
François FAGES, Lifeware, INRIA Paris-Rocquencourt
Éric FANCHON, TIMC-IMAG, CNRS & Université Joseph Fourier de Grenoble
Jérôme FERET, Antique, INRIA-Rocquencourt & ÉNS
Dan GOREAC, LAMA, Université Paris-Est Marne-la-Vallée
Cédric LHOUSSAINE, Cristal, Université Lille 1
Guillaume MADELAINE, Cristal, Université Lille 1
Tarek MELLITI, IBISC, Université d'Évry - Val d'Essonne
Aurélien NALDI, DIMNP, Université Montpellier 2
Joachim NIEHREN, Cristal, INRIA-Lille
Loïc PAULEVÉ, LRI, CNRS & Université Paris Sud
Kévin PERROT, LIF, Aix-Marseille Université
Ovidiu RADULESCU, DIMNP, Université de Montpellier
Élisabeth REMY, I2M, Aix-Marseille Université
Adrien RICHARD, I3S, CNRS & Université de Nice - Sophia Antipolis
Sylvain SENÉ, LIF, Aix-Marseille Université
Anne SIEGEL, IRISA, CNRS & Université de Rennes
Laurent TOURNIER, INRA Jouy en Josas