DReSS: A difference measurement based on reachability between state spaces of Boolean networks

Ziqiao Yin, Binghui Guo, Shuangge Ma, Yifan Sun, Zhilong Mi, Zhiming ZhengbioRxiv 2020 · DOI

TL;DR

This paper introduces DReSS, a novel quantitative measure to assess how structural changes in biological regulatory networks alter their state spaces. DReSS focuses on reachability differences and reveals that perturbations primarily affect internal state transitions rather than the overall set of attractors.

What Problem Does This Paper Address?

Biological systems are dynamic and their regulatory networks can change due to internal biological factors or external data-related issues. These "structural perturbations" can significantly alter how a system behaves. A key aspect of this behavior is "reachability" – whether one state can evolve into another. While researchers study the impact of perturbations, there's been a lack of a quantitative method to precisely measure how these structural changes affect the reachability landscape of a system's state space. This paper aims to fill that gap by proposing DReSS.

Methods

The core of the paper is the development of DReSS (Difference based on Reachability between State Spaces). DReSS quantifies the difference between the state spaces of two Boolean networks (representing the system before and after perturbation). This is achieved by:

  1. Modified Reachability Matrix ($\tilde{R}$): Unlike traditional reachability matrices, this modified version accounts for attractors (stable states or limit cycles) by setting diagonal elements to 1 only if a state is part of an attractor.
  2. Hamming Distance: The Hamming distance is used to compare the modified reachability matrices of the two state spaces.
  3. DReSS Calculation: DReSS is defined as the normalized Hamming distance between the modified reachability matrices of the two state spaces ($DRESS(S_G, S_{G'}) = \frac{Hamming(\tilde{R}_{S_G}, \tilde{R}_{S_{G'}})}{N^2}$).
  4. Derived Indices:
    • diagDReSS: Focuses specifically on the diagonal elements of the modified reachability matrices to measure differences in attractor sets.
  5. iDReSS: A vertex centrality measure that identifies sensitive positions in the network by considering the DReSS values of perturbations related to that vertex.

The authors also prove that DReSS exhibits desirable properties like non-negativity, symmetry, and subadditivity.

Datasets

The primary dataset used for evaluation is the yeast cell cycle regulatory network. The authors also compare results against random networks (ER random network, BA scale-free network, and WS small world network) to contextualize their findings.

Key Insights and Ideas

  • Reachability is Key: The paper highlights reachability as a crucial dynamical feature of biological systems and a sensitive indicator of structural changes.
  • Beyond Attractors: While attractors are important, DReSS reveals that perturbations can significantly alter the pathways between states and within attractor basins, not just the attractors themselves.
  • DReSS vs. Traditional Metrics: DReSS offers a more nuanced view than traditional graph difference measurements, which often treat all nodes equally. DReSS accounts for the ordered nature of states and their unique roles.
  • Sensitive vs. Robust Positions: The analysis of iDReSS in the yeast cell cycle network suggests that biological networks have distinct positions that are either sensitive to perturbations or designed for robustness.

Key Results

  • DReSS Quantifies Perturbation Impact: DReSS successfully quantifies the impact of structural perturbations on the state space of Boolean networks.
  • Perturbations Affect Internal Dynamics: Analysis of the yeast cell cycle network shows that structural perturbations lead to significant DReSS values, indicating changes in reachability. However, diagDReSS values remain largely similar between real and random networks, suggesting that attractors themselves are not significantly affected.
  • Real Networks are More Dispersed: DReSS distributions in real biological networks are more dispersed than in random networks, indicating a clearer role assignment for different network positions in responding to or maintaining robustness against perturbations.
  • Sensitive Vertex Identification: iDReSS successfully identifies sensitive vertices in the yeast cell cycle network, such as SK, CDC2/CDC13, and SLP1, which are biologically relevant.

Limitations and Future Work

  • Computational Complexity: Calculating DReSS for large systems can be computationally intensive, with complexity scaling with the number of states ($N=2^n$). The authors suggest simplification methods like network module partitioning or random seed sampling for approximation.
  • Theoretical Distribution: The paper mentions that future research could focus on the theoretical distribution of DReSS to more easily identify significant positions.
  • Optimal Control: Combining DReSS with optimization theory could lead to new methods for finding optimal control strategies for biological systems, aiming to guide them to desired stable states with minimal cost.
  • Broader Applications: The authors suggest that DReSS can be used to evaluate the influence of specific positions in a network, regardless of whether an edge is currently known to exist there.

Summary updated

Abstract

Abstract Researches on dynamical features of biological systems are mostly based on fixed network structure. However, both biological factors and data factors can cause structural perturbations to biological regulatory networks. There are researches focus on the influence of such structural perturbations to the systems’ dynamical features. Reachability is one of the most important dynamical features, which describe whether a state can automatically evolve into another state. However, there is still no method can quantitively describe the reachability differences of two state spaces caused by structural perturbations. DReSS, Difference based on Reachability between State Spaces, is proposed in this research to solve this problem. First, basic properties of DReSS such as non-negativity, symmetry and subadditivity are proved based on the definition. And two more indexes, diagDReSS and iDReSS are proposed based on the definition of DReSS. Second, typical examples like DReSS = 0 or 1 are shown to explain the meaning of DReSS family, and the differences between DReSS and traditional graph distance are shown based on the calculation steps of DReSS. Finally, differences of DReSS distribution between real biological regulatory network and random networks are compared. Multiple interaction positions in real biological regulatory network show significant different DReSS value with those in random networks while none of them show significant different diagDReSS value, which illustrates that the structural perturbations tend to affect reachability inside and between attractor basins rather than to affect attractor set itself. Author summary Boolean network is a kind of networks which is widely used to model biological regulatory systems. There are structural perturbations in biological systems based on both biological factors and data-related factors. We propose a measurement called DReSS to describe the difference between state spaces of Boolean networks, which can be used to evaluate the influence of specific structural perturbations of a network to its state space quantitively. We can use DReSS to detect the sensitive interactions in a regulatory network, where structural perturbations can influence its state space significantly. We proved properties of DReSS including non-negativity, symmetry and subadditivity, and gave examples to explain the meaning of some special DReSS values. Finally, we present an example of using DReSS to detect sensitive vertexes in yeast cell cycle regulatory network. DReSS can provide a new perspective on how different interactions affect the state space of a specific regulatory network differently.
BibTeX
@misc{yin2020dress,
  author = {Ziqiao Yin and Binghui Guo and Shuangge Ma and Yifan Sun and Zhilong Mi and Zhiming Zheng},
  title = {{DReSS: A difference measurement based on reachability between state spaces of Boolean networks}},
  year = {2020},
  doi = {10.1101/2020.06.19.161224},
  howpublished = {bioRxiv},
}

Loading related content...

Figure