Séminaire de Sara Riva - Université de Bordeaux
Synthesis and Reprogramming of Boolean networks: a QBF problem
4 mai 2023 - 14:00Boolean networks (BNs) are discrete dynamical systems (DDSs) with applications to the modeling of cellular behaviors, such as cellular differentiation and fate decision processes. These models represent the long-term (i.e., fixed points and attractors) and the transient behaviors of the studied phenomena. The synthesis of Boolean networks aims to provide an automatic way of obtaining networks that satisfy the constraints derived from knowledge of the phenomenon. Usually, this knowledge consists of information on the structure of the interaction graph or on the possible states and transitions between the states of the system to be modeled. BNs can be updated according to different techniques (such as synchronous, asynchronous, or most permissive) able to generate different dynamics. However, it is common to be interested in properties of the long-term dynamics independently from the update procedure. Minimal trap spaces are useful to study the attractors in this scenario. Modeling a cellular process using BN is useful also to study possible permutations capable of destabilizing the system or capable of bringing dynamic behavior toward stable states that respect certain properties (called markers). These are in fact among the objectives of BN control or BN reprogramming.
It has been shown that by using Answer-Set Programming-based approaches, it is possible to solve some variations of the marker reprogramming problem, where the perturbations consist of fixing a set of components to a fixed value. ASP can be employed for efficiently solving ∃- and ∃∀-expressions. However, when studying the reprogramming problems on attractors of BNs (i.e., minimal trap spaces), the expressive capacity of ASP is exceeded. The same problem appears when the goal is to enable Boolean Networks synthesis starting from universal properties on their minimal trap spaces. It thus becomes interesting to understand how we can model and solve these problems efficiently.