Search

International audience; Boolean network modeling of gene regulation but also of post-transcriptomic systems has proven over the years that it can bring powerful analyses and corresponding insight to the many cases where precise biological data is not sufficiently available to build a detailed quantitative model. Besides simulation, the analysis of such models is mostly based on attractor computation, since those correspond roughly to observable biological phenotypes.The recent use of trap spaces made a real breakthrough in that field allowing to consider medium-sized models that used to be out of reach. However,with the continuing increase in model size and complexity of Boolean update functions, the state-of-the-art computation of minimal trap spaces based onprime implicants shows its limits due to the difficulty of the prime-implicant computation. In this article we explore and prove for the first time a connection between trap spaces of a general Boolean network and siphons of its Petri net encoding. Besides important theoretical applications in studying propertiesof trap spaces, the connection enables us to propose an alternative approach to compute minimal trap spaces, and hence complex attractors, of a generalBoolean network. It replaces the need for prime implicants by a completely different technique, namely the enumeration of maximal siphons in the Petri net encoding of the original model. We then demonstrate its efficiency and compare it to the state-of-the-art methods on a large collection of real-world and randomly generated models.

International audience; Boolean modelling of gene regulation but also of post-transcriptomic systems has proven over the years that it can bring powerful analyses and corresponding insight to the many cases where precise biological data is not sufficiently available to build a detailed quantitative model. This is even more true for very large models where such data is frequently missing and led to a constant increase in size of logical models à la Thomas. Besides simulation, the analysis of such models is mostly based on attractor computation, since those correspond roughly to observable biological phenotypes. The recent use of trap spaces made a real breakthrough in that field allowing to consider medium-sized models that used to be out of reach. However, with the continuing increase in model-size, the state-of-the-art computation of minimal trap spaces based on prime-implicants shows its limits as there can be a huge number of implicants.In this article we present an alternative method to compute minimal trap spaces, and hence complex attractors, of a Boolean model. It replaces the need for prime-implicants by a completely different technique, namely the enumeration of maximal siphons in the Petri net encoding of the original model. After some technical preliminaries, we expose the concrete need for such a method and detail its implementation using Answer Set Programming. We then demonstrate its efficiency and compare it to implicant-based methods on some large Boolean models from the literature.

International audience; Boolean models of physical or biological systems describe the global dynamics of the system and their attractors typically represent asymptotic behaviors. In the case of large networks composed of several modules, it may be difficult to identify all the attractors. To explore Boolean dynamics from a novel viewpoint, we will analyse the dynamics emerging from the composition of two known Boolean modules. The state transition graphs and attractors for each of the modules can be combined to construct a new asymptotic graph which will (1) provide a reliable method for attractor computation with partial information ; (2) illustrate the differences in dynamical behavior induced by the updating strategy (asynchronous, synchronous, or mixed); and (3) show the inherited organization/structure of the original network's state transition graph.

Boolean networks with asynchronous updates are a class of logical models particularly well adapted to describe the dynamics of biological networks with uncertain measures. The state space of these models can be described by an asynchronous state transition graph, which represents all the possible exits from every single state, and gives a global image of all the possible trajectories of the system. In addition, the asynchronous state transition graph can be associated with an absorbing Markov chain, further providing a semi -quantitative framework where it becomes possible to compute probabilities for the different trajectories. For large networks, however, such direct analyses become computationally untractable, given the exponential dimension of the graph. Exploiting the general modularity of biological systems, we have introduced the novel concept of asymptotic graph, computed as an interconnection of several asynchronous transition graphs and recovering all asymptotic behaviors of a large interconnected system from the behavior of its smaller modules. From a modeling point of view, the interconnection of networks is very useful to address for instance the interplay between known biological modules and to test different hypotheses on the nature of their mutual regulatory links. This paper develops two new features of this general methodology: a quantitative dimension is added to the asymptotic graph, through the computation of relative probabilities for each final attractor and a companion cross-graph is introduced to complement the method on a theoretical point of view.