Une vision et des portes en chemin...

My current research aims at developing computational methods for understanding the cell machinery and establishing formal paradigms in cell biology. It is based on the vision of cells as computation, and on the use of concepts and tools from theoretical computer science to master the complexity of cell processes. While for the biologist, as well as for the mathematician, the sizes of the biological networks and the number of elementary interactions constitute a complexity barrier, for the computer scientist the difficulty is not that much in the size of the networks than in the unconventional nature of biochemical computation. Unlike most programs, biochemical computation involves transitions that are stochastic rather than deterministic, continuous-time rather than discrete- time, poorly localized in compartments instead of well-structured in modules, and created by evolution instead of by rational design.

Logical paradigm for systems biology

My first idea in 2002 was to design a dedicated rule-based language to model biochemical reaction systems and analyze their Boolean dynamics using symbolic model-checking tools developed for circuit and program analysis. I generalized this approach to quantitative models with the following logical paradigm for systems biology:

biological system = state transition system

biological property = temporal logic formula

model validation = model-checking, robustness

model inference = temporal logic constraint solving

In order to efficiently deal with parameter inference problems and robustness measures, we have generalized model-checking to temporal logic constraint solving, by considering temporal logic formulae with free variables over some domain D, and by computing a validity domain for the variables rather than a truth value for the formula. When D is a metric space, this allows us to define a continuous degree of satisfaction for a temporal logic formula in a given Kripke structure, opening up the field of model-checking to optimization. This has been implemented in BIOCHAM, and used in various contexts to infer unknown kinetic parameter values from temporal logic properties in high dimensional systems (up to 100 parameters), and decipher complex biochemical processes.

Cell signalling

In collaboration with Eric Reiter (CNRS-INRA) and Frédérique Clément (SISYPHE team) and with Robert Lefkowitz (Duke University), recipient of the Nobel prize in Chemistry 2012 for his work on G-Protein Coupled Receptors (GPCR), we have combined experimental approaches with computational modeling in BIOCHAM to decipher the molecular mechanisms as well as the unexplained complex dynamics governing GPCR signaling. This signal balancing mechanism is found to be relevant to a wide range of important drug targets composed of other seven-transmembrane receptors.

  • An ODE-based dynamical model of ERK activation by the prototypical angiotensin II type-1A seven transmembrane receptor has been built and validated using BIOCHAM
  • In order to deal with a limited number of experimental read-outs, unknown parameters have been inferred by simultaneously fitting control and perturbed conditions expressed in temporal logic LTL(R lin ) in BIOCHAM using the covariance method adaptive evolution strategy (CMAES) for continuous optimization (EPI TAO)
  • In addition to its well-established function in G-protein uncoupling, G protein-coupled receptor kinase 2 has been shown to exert a strong negative effect on β-arrestin-dependent signaling and by doing so, to balance G-protein and β-arrestin signaling. The failure to fit some temporal constraints was the key to infer the existence of these interactions from the computational model.
  • Domitille Heitzler, Guillaume Durand, Nathalie Gallay, Aurélien Rizk, Seungkirl Ahn, Jihee Kim, Jonathan D. Violin, Laurence Dupuy and Christophe Gauthier, Vincent Piketty, Pascale Crépieux, Anne Poupon, Frédérique Clément, François Fages, Robert J. Lefkowitz, Eric Reiter. Competing G protein-coupled receptor kinases balance G protein and β-arrestin signaling. Molecular Systems Biology, 8(590), 2012.

Cell cycle regulation and cancer chronotherapeutics

Recent advances in cancer chronotherapy techniques support the evidence that there exist important links between the cell cycle regulation and the circadian clock genes. One purpose for modeling these links is to better understand how to efficiently target malignant cells depending on the phase of the day and patient characteristics. This is at the heart of our collaboration with Francis Lévi, CNRS-INSERM, Hopital Paul Brousse, Villejuif, and previous participation to two european projects on this theme. Currently, we investigate the effect of transcription inhibition during mitosis, as a reverse coupling from the cell cycle to the circadian clock. We use temporal logic constraints and the parallel version of BIOCHAM for parameter search, running on the Jade cluster of 10000 processors at the GENCI CINES, to couple dynamical models in high dimension and fit models to experimental data time series obtained in Franck Delaunay's lab in Nice, CNRS.

Model reduction by subgraph epimorphism

The subgraph epimorphism (SEPI) problem is a variant of graph matching problem. Our interest in SEPIs stems from the study of model reductions in systems biology, where large systems of biochemical reactions can be naturally represented by bipartite digraphs of species and reactions. We have shown last year that in this setting, the notion of model reduction can be formalized as the existence of a sequence of vertex deletion and merge operations that transforms a first reaction graph into a second graph. This problem is in turn equivalent to the existence of a subgraph (corresponding to delete operations) epimorphism (i.e. surjective homomorphism, corresponding to merge operations) from the first graph to the second.

We have shown that the SEPI existence problem between two graphs is NP-complete but that constraint logic programming can be successfully used to solve SEPI matching problems on a large benchmark of reaction graphs extracted from the repository of systems biology models

Now, we study the mathematical conditions under which SEPI reductions are justified, in the framework of tropical algebra to determine the dominating monomials, and using constraint logic programming to solve tropical equilibration problems.

Constraint logic programming

Constraint logic programming is a declarative programming paradigm based on mathematical logic with the following identifications:

program = logical formula

execution = proof search

In Constraint Satisfaction Problems (CSP), the logical formulae are conjunctions of constraints (i.e. relations on variables expressing partial information) and the satisfiability proofs are computed by constraint solving procedures. In Constraint Logic Programming (CLP), the logical formulae are Horn clauses with constraints (i.e. Prolog one headed rules for the inductive definitions of relations on variables) and the satisfiability proofs combine constraint solving and clause resolution. We use them for solving combinatorial problems and for implementing Biocham.

Because of the importance of optimization techniques in our research in computational systems biology, both constraint programming methods for computing with partial information systems and solving hard combinatorial static analysis problems, and continuous optimization methods for dealing with continuous parameters, I keep some activity purely dedicated to optimization problems, such as bin packing and placement problems in collaboration with the Tasc group and SME KLS-optim, or energy optimization problems with General Electric Transportation. The objective is to develop optimization algorithms for biological problems at the right level of generality, allowing comparisons with other methods, confrontations to other problems, and better insight on the optimization processes which are sometimes easier to visualize on other problems (e.g. packing).

  • Thierry Martinez, François Fages, Abder Aggoun. A Stochastic Continuous Optimization Backend for MiniZinc with Applications to Geometrical Placement Problems. In Proceedings of the 13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR'16, 2016. [ preprint ]

  • Thierry Martinez, François Fages, Sylvain Soliman. Search by Constraint Propagation. In Proceedings of the 17th International Conference on Principles and Practice of Declarative Programming, PPDP'15, pages 173–183. ACM, 2015. [ preprint ]

  • Thierry Martinez, Lumadaiara Vitorino, François Fages, Abderrahmane Aggoun. On Solving Mixed Shapes Packing Problems by Continuous Optimization with the CMA Evolution Strategy. In Proceedings of the first Computational Intelligence BRICS Congress BRICS-CCI'13, pages 515–521. IEEE Press, 2013. [ preprint ]

  • François Fages, Julien Martin. From Rules to Constraint Programs with the Rules2CP Modelling language. In Recent Advances in Constraints, Revised Selected Papers of the 13th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP'08, pages 66–83, volume 5655 of Lecture Notes in Artificial Intelligence. Springer-Verlag, 2009. [ preprint ]

  • François Fages, Akash Lal. A Constraint Programming Approach to Cutset Problems. Journal Computers and Operations Research, 33:10:2852–2865, 2006. [ preprint ]

  • Emmanuel Coquery, François Fages. Subtyping constraints in quasi-lattices. In Proceedings of the 23rd conference on foundations of software technology and theoretical computer science, FSTTCS'2003, pages 136–148, volume 2914 of Lecture Notes in Computer Science. Springer-Verlag, 2003. [ preprint ]

  • François Fages, Emmanuel Coquery. Typing Constraint Logic Programs. Journal of Theory and Practice of Logic Programming, 1(6):751–777, 2001. [ preprint ]

  • François Fages, Paul Ruet, Sylvain Soliman. Linear concurrent constraint programming: operational and phase semantics. Information and Computation, 165(1):14–41, 2001. [ preprint ]