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

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 system's 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. We illustrate the insights and predictions that arise from the SD Markov chain by analyzing a published model of cancer cell metastasis. 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.