Semantics of Boolean Networks

Level: M2

Contact: Philippe Dague <philippe.dague [at] universite-paris-saclay [dot] fr>, Thomas Chatain <thomas.chatain [at] ens-paris-saclay [dot] fr>

Location: Laboratoire Méthodes Formelles, Université Paris-Saclay

Keywords: Boolean Networks, update modes


Since their introduction in the late 1960s [7], logical models, such as Boolean Networks (BNs), have been widely adopted for reasoning about signaling and gene networks as they require few parameters and can easily integrate information from omics datasets and genetic screens. These models represent processes with a high degree of generalization and can offer coarse-grained but robust predictions, which makes them particularly suitable for large biological networks. BNs are formal discrete dynamical systems with notorious applications for modeling cellular differentiation and fate decision processes: the attractors capture the stable behaviors and the trajectories capture the transient dynamics of the cell. To each BN is attached its interaction graph that references the positive and negative influences between components and hence is a compact and static abstraction of the BN dynamics [4]. Also, methods based on a generalization of the steady state notion, the so-called trap spaces, can be exploited to investigate attractor properties as well as for model reduction techniques [2].

Given a BN, i.e., n local functions from Bn to B, where B = {0, 1} is the Boolean domain, the update mode specifies how to compute the next configuration from the present one. There is a vast zoo of update modes [1, 5], but traditionally, two modes are usually considered in biological modeling: the synchronous (or parallel) deterministic mode, where the next configuration results from the simultaneous application of all n local functions, and the fully asynchronous where the next configuration results from the application of only one local function, chosen non-deterministically. However, (a)synchronous update modes do not lead to a complete qualitative abstraction of quantitative systems and preclude the prediction of trajectories that are actually feasible when considering time scales or concentration scales. The Most Permissive (MP) [3, 6] is a recently-introduced update mode that brings the formal guarantee to capture any trajectory that is feasible by any quantitative system compatible with the Boolean network. In addition, the MP update mode benefits from much better complexity results than the traditional update modes for all current problems, e.g., the problem of reachability between configurations, which is PSPACE-complete for the latter ones, becomes PNP (even P with local monotonicity assumption) for it.


Despite its good properties, the MP update mode appears sometimes “too permissive”. Allowing spurious, i.e., not feasible in practice, behaviors is quite normal for any abstraction of a given problem, nevertheless one would want to eliminate the most obvious of them. In particular, those which are not consistent w.r.t. the “local context”, i.e., that differ at two different occurrences of the same context. For example, it may appear legitimate to require that an (unknown but fixed) order is maintained, inside any given component, between the thresholds of activation/inhibition by this component of all the components it influences, or else a fixed time order of the crossing of those thresholds by the variables involved along the trajectory all else being equal.

The objective is thus to define, study and classify such BN update modes, that would take place between the so-called Interval update mode and the MP update mode in the updating mode hierarchy, taking care that they keep the property of the MP update mode to capture any quantitatively feasible trajectory and offer better complexity results than the traditional update modes (even if some degradation w.r.t. the MP update mode could be admissible).


Skills in formal methods. Knowledge to acquire about BNs. Possibly use of a logic-based programming language for experimentation, such as ASP (Answer Set Programming).


  • Philippe Dague, Professeur émérite Université Paris-Saclay ( et
  • Thomas Chatain, Maître de conférences HDR ENS Paris-Saclay (


[1] Thomas Chatain, Stefan Haar, Juraj Kolčák, Loïc Paulevé, and Aalok Thakkar. “Concurrency in Boolean networks”. In: Natural Computing 19.1 (2020), pp. 91–109.

[2] Hannes Klarner, Alexander Bockmayr, and Heike Siebert. “Computing maximal and minimal trap spaces of Boolean networks”. In: Natural Computing 14.4 (2015), pp. 535–544.

[3] Loïc Paulevé, Juraj Kolčák, Thomas Chatain, and Stefan Haar. “Reconciling qualitative, abstract, and scalable modeling of biological networks”. In: Nature Communications 11.1 (2020), p. 4256.

[4] Loïc Paulevé and Adrien Richard. “Static analysis of Boolean networks based on interaction graphs: a survey”. In: Electronic Notes in Theoretical Computer Science 284 (2012), pp. 93–104.

[5] Loïc Paulevé and Sylvain Sené. “Boolean networks and their dynamics: the impact of updates”. In: Systems Biology Modelling and Analysis: Formal Bioinformatics Methods and Tools. Wiley, 2022.

[6] Loïc Paulevé and SylvainSené. “Non-Deterministic Updates of Boolean Networks”. In: 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Ed. by Alonso Castillo-Ramirez, Pierre Guillon, and Kevin Perrot. Vol. 90. Open Access Series in Informatics (OASIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, 10:1–10:16.

[7] René Thomas. “Boolean formalization of genetic control circuits”. In: Journal of theoretical biology 42.3 (1973), pp. 563–585.

Download topic in PDF