Succession-diagram-based Markov chains reveal the attractor landscape of asynchronous Boolean networks

Abstract

Comprehensive analysis of the dynamics of Boolean models of biological systems is hampered by the exponentially large state space. Here we introduce the succession-diagram-based Markov chain (SD Markov chain), a coarse-grained representation that uses trap spaces (unescapable state subspaces) of the Boolean model as the states of a Markov chain. These trap spaces and their succession diagram can be efficiently identified, and constitute a dramatic reduction compared to the full state space. The SD Markov chain preserves the decisions that trap the systems dynamics while making the state space computationally tractable. Using an ensemble of random Boolean networks with known state transition matrices, we show that the SD Markov chain accurately reproduces attractors, basins of attraction, convergence probabilities, decision transitions, and sequences of events. By combining the interpretability of the succession diagram with the probabilistic rigor of Markov analysis, the SD Markov chain offers a compact quantitative description of the attractor landscape and provides a new avenue for studying control and stability in complex biological systems.