Capturing dynamic relevance in Boolean networks using graph theoretical measures

Abstract

Motivation: Interaction graphs are able to describe regulatory dependencies between compounds without capturing dynamics. In contrast, mathematical models that are based on interaction graphs allow to investigate the dynamics of biological systems. However, since dynamic complexity of these models grows exponentially with their size, exhaustive analyses of the dynamics and consequently screening all possible interventions eventually becomes infeasible. Thus, we designed an approach to identify dynamically relevant compounds based on the static network topology.

Results: Here, we present a method only based on static properties to identify dynamically influencing nodes. Coupling vertex betweenness and determinative power, we could capture relevant nodes for changing dynamics with an accuracy of 75% in a set of 35 published logical models. Further analyses of the selected compounds' connectivity unravelled a new class of not highly connected nodes with high impact on the networks' dynamics, which we call gatekeepers. We validated our method's working concept on logical models, which can be readily scaled up to complex interaction networks, where dynamic analyses are not even feasible.

Availability and implementation: Code is freely available at https://github.com/sysbio-bioinf/BNStatic.

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

Schematic description of the approach. Using a combination of the two graph-based measures VB and DP on the interaction graph allows to predict dynamic behaviour and nodes most relevant for that (right). Traditional approaches rely on certain dynamic models such as Boolean networks (left). These models are used to simulate the dynamics under various perturbation scenarios such as knock-out or overexpression to determine the most relevant nodes. In contrast, due to the smaller search space, the interaction graph-based approach allows to screen for these nodes more efficiently

Fig. 2.

Static measures to determine important dynamic nodes. (A) The figure shows the sensitivity (red) and specificity (blue) yield by the comparison of static measures (vertex betweenness and determinative power) and the average of the three dynamic parameters at each threshold T = {1,…,100} over all networks. Dots represent the average sensitivity and specificity and coloured regions display the standard deviations. Here, the point of intersection between sensitivity and specificity is at 0.756 corresponding to a threshold T = 73%. (B) The performance of the intersection against single dynamic measures is depicted at each threshold T = {1,…,100}. The figure shows that considering single dynamic measures (Hamming distance in purple, attractor loss in brown, attractor gain in green) is comparable to using their average value

Fig. 3.

Characterization of selected nodes. (A) Percentile scores of static impacts. Selected nodes from the intersection of the two static measures vertex betweenness and determinative power are further divided in hubs, positive mismatches and negative mismatch nodes (n). Hub nodes are shown to have a higher percentile score in static ranking. (B) Impact on dynamic ranking. The percentile score in dynamic impact for each of the selected and non-selected subgroups is depicted. Hubs and positive mismatch nodes have comparable dynamic impact whereas negative mismatches and none selected have significantly reduced impact. (C) Connectivity defined by the z-score is depicted for the selected and none selected subgroups. Positive mismatches show significantly lower connectivity compared to hubs and negative mismatches. (D) Average maximal mutual information (MI) in paths (p) to hubs. Positive mismatch nodes show a significantly higher MI then negative mismatches and not selected nodes. Statistical tests were performed using a Bonferroni corrected Wilcoxon rank sum test. Significant values are considered for p < 0.05