# Research

*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 and artificial intelligence to master the complexity of cell processes.

François Fages. Artificial Intelligence in Biological Modeling. In

*A Guided Tour of Artificial Intelligence Research*. Springer-Verlag, 2017. [ preprint ]

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.

### Chemical Reaction Network Theory, Analysis and Synthesis

Feinberg’s chemical reaction network theory and Thomas’s influence network analyses provide sufficient and/or necessary structural conditions for the existence of multiple steady states and oscillations in regulatory networks. Those conditions can be verified by static analyzers without knowing kinetic parameter values nor making any simulation. In this domain, most of our work consists in analyzing the interplay between the structure (Petri net properties, influence graph, subgraph epimorphisms) and the dynamics (Boolean, CTMC, ODE, time scale separations) of biochemical reaction systems.

Adrien Baudier, François Fages, Sylvain Soliman. Graphical Requirements for Multistationarity in Reaction Networks and their Verification in BioModels.

*Journal of Theoretical Biology*, 459:79–89, 2018. [ preprint ]François Fages, Thierry Martinez, David Rosenblueth, Sylvain Soliman. Influence Networks compared with Reaction Networks: Semantics, Expressivity and Attractors.

*IEEE/ACM Transactions on Computational Biology and Bioinformatics*, 2018. [ preprint ]Fages, François, Le Guludec, Guillaume and Bournez, Olivier, Pouly, Amaury. Strong Turing Completeness of Continuous Chemical Reaction Networks and Compilation of Mixed Analog-Digital Programs. In

*CMSB'17: Proceedings of the fiveteen international conference on Computational Methods in Systems Biology*, pages 108–127, volume 10545 of*Lecture Notes in Computer Science*. Springer-Verlag, 2017. [ preprint ]François Fages, Steven Gay, Sylvain Soliman. Inferring Reaction Systems from Ordinary Differential Equations.

*Theoretical Computer Science*, 599:64–78, 2015. [ preprint ]François Fages. Cells as Machines: towards Deciphering Biochemical Programs in the Cell (Invited Talk). In

*Proc. 10th International Conference on Distributed Computing and Internet Technology ICDCIT'14*, pages 50–67, volume 8337 of*Lecture Notes in Computer Science*. Springer-Verlag, 2014. [ preprint ]François Fages, Sylvain Soliman. Formal Cell Biology in BIOCHAM. In

*8th Int. School on Formal Methods for the Design of Computer, Communication and Software Systems: Computational Systems Biology SFM'08*, pages 54–80, volume 5016 of*Lecture Notes in Computer Science*. Springer-Verlag, 2008. [ preprint ]François Fages, Sylvain Soliman. From reaction models to influence graphs and back: a theorem. In

*Proceedings of Formal Methods in Systems Biology FMSB'08*,*Lecture Notes in Computer Science*. Springer-Verlag, 2008. [ preprint ]François Fages, Sylvain Soliman. Abstract Interpretation and Types for Systems Biology.

*Theoretical Computer Science*, 403(1):52–70, 2008. [ preprint ]

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

Fages, François, Soliman, Sylvain. On Robustness Computation and Optimization in BIOCHAM-4. In

*CMSB'18: Proceedings of the sixteenth international conference on Computational Methods in Systems Biology*,*Lecture Notes in BioInformatics*. Springer-Verlag, 2018. [ preprint ]Pauline Traynard, François Fages, Sylvain Soliman. Trace Simplifications preserving Temporal Logic Formulae with Case Study in a Coupled Model of the Cell Cycle and the Circadian Clock. In

*CMSB'14: Proceedings of the twelth international conference on Computational Methods in Systems Biology*, pages 114–128,*Lecture Notes in BioInformatics*. Springer-Verlag, 2014. [ preprint ] [ slides ]François Fages, Pauline Traynard. Temporal Logic Modeling of Dynamical Behaviors: First-Order Patterns and Solvers. In

*Logical Modeling of Biological Systems*, pages 291–323. John Wiley Sons, Inc., 2014. [ preprint ]Aurélien Rizk, Grégory Batt, François Fages, Sylvain Soliman. Continuous Valuations of Temporal Logic Specifications with applications to Parameter Optimization and Robustness Measures.

*Theoretical Computer Science*, 412(26):2827–2839, 2011. [ preprint ]Aurélien Rizk, Grégory Batt, François Fages, Sylvain Soliman. A general computational method for robustness analysis with applications to synthetic gene networks.

*Bioinformatics*, 12(25):il69–il78, 2009.François Fages, Aurélien Rizk. From Model-Checking to Temporal Logic Constraint Solving. In

*Proceedings of CP'2009, 15th International Conference on Principles and Practice of Constraint Programming*, pages 319–334,*Lecture Notes in Computer Science*. Springer-Verlag, 2009. [ preprint ]François Fages, Aurélien Rizk. On Temporal Logic Constraint Solving for the Analysis of Numerical Data Time series.

*Theoretical Computer Science*, 408(1):55–65, 2008. [ preprint ]Laurence Calzone, Nathalie Chabrier-Rivier, François Fages, Sylvain Soliman. Machine learning biochemical networks from temporal logic properties. In

*Transactions on Computational Systems Biology VI*, pages 68–94, volume 4220 of*Lecture Notes in BioInformatics*. Springer-Verlag, 2006. [ preprint ]Nathalie Chabrier, François Fages. Symbolic model checking of biochemical networks. In

*CMSB'03: Proceedings of the first workshop on Computational Methods in Systems Biology*, pages 149–162, volume 2602 of*Lecture Notes in Computer Science*. Springer-Verlag, 2003. [ preprint ]

### Model reductions

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 biomodels.net.

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.

Sylvain Soliman, François Fages, Ovidiu Radulescu. A constraint solving approach to model reduction by tropical equilibration.

*Algorithms for Molecular Biology*, 9(24), 2014.Steven Gay, François Fages, Thierry Martinez, Sylvain Soliman, Christine Solnon. On the subgraph Epimorphism Problem.

*Discrete Applied Mathematics*, 162:214–228, 2014. [ preprint ]Steven Gay, Sylvain Soliman, François Fages. A Graphical Method for Reducing and Relating Models in Systems Biology.

*Bioinformatics*, 26(18):i575–i581, 2010.

### Synthetic biology

In collaboration with Franck Molina (CNRS, Sys2Diag, Montpellier) and Jie-Hong Jiang (NTU, Taiwan) we ambition to apply our techniques to the design and implementation of biosensors in non-living vesicles for medical applications. Our approach is based on purely protein computation and on our ability to compile con- trollers and programs in biochemical reactions. The realization will be prototyped using a microfluidic device at CNRS Sys2Diag which will allow us to precisely control the size of the vesicles and the concentrations of the injected proteins. It is worth noting that the choice of non-living chassis, in contrast to living cells in synthetic biology, is particularly appealing for security considerations and compliance to forthcoming EU regulation.

Alexis Courbet, Patrick Amar, François Fages, Eric Renard, Franck Molina. Computer-aided biochemical programming of synthetic microreactors as diagnostic devices.

*Molecular Systems Biology*, 14(4), 2018. [ preprint ]Fages, François, Le Guludec, Guillaume and Bournez, Olivier, Pouly, Amaury. Strong Turing Completeness of Continuous Chemical Reaction Networks and Compilation of Mixed Analog-Digital Programs. In

*CMSB'17: Proceedings of the fiveteen international conference on Computational Methods in Systems Biology*, pages 108–127, volume 10545 of*Lecture Notes in Computer Science*. Springer-Verlag, 2017. [ preprint ]Tai-Yin Chiu, Hui-Ju K. Chiang, Ruei-Yang Huang , Jie-Hong R. Jiang, François Fages. Synthesizing Configurable Biochemical Implementation of Linear Systems from Their Transfer Function Specifications.

*PLoS ONE*, 10(9):e0137442, 2015.

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

Pauline Traynard, François Fages, Sylvain Soliman. Model-based Investigation of the Effect of the Cell Cycle on the Circadian Clock through Transcription Inhibition during Mitosis. In

*CMSB'15: Proceedings of the thirteenth international conference on Computational Methods in Systems Biology*, pages 208–221, volume 9308 of*Lecture Notes in BioInformatics*. Springer-Verlag, 2015. [ preprint ]Elisabetta De Maria, François Fages, Aurélien Rizk, Sylvain Soliman. Design, Optimization, and Predictions of a Coupled Model of the Cell Cycle, Circadian Clock, DNA Repair System, Irinotecan Metabolism and Exposure Control under Temporal Logic Constraints.

*Theoretical Computer Science*, 412(21):2108–2127, 2011. [ preprint ]Jean Clairambault, François Fages, Sylvain Soliman. Patient-tailored cancer therapeutics - The TEMPO Project.

*ERCIM News*, 69:24–25, 2007. [ preprint ]Nathalie Chabrier-Rivier, Marc Chiaverini, Vincent Danos, François Fages, Vincent Schächter. Modeling and querying biochemical interaction networks.

*Theoretical Computer Science*, 325(1):25–44, 2004. [ preprint ]

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

### 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 ]