Measuring rank robustness in scored protein interaction networks

Lyuba V. Bozhilova, Alan Whitmore, Jonny Wray, Gesine Reinert, Charlotte M. DeaneBMC Bioinformatics 2019 · DOI · OpenReview

Introduction

In systems biology, Protein-Protein Interaction Networks (PINs) serve as essential maps for navigating cellular complexity. However, these maps are inherently "fuzzy" due to the noisy nature of experimental data. To manage this, researchers typically use "confidence scores" to filter interactions, selecting a threshold—such as 0.4 or 0.7—to determine which edges are included in the analysis. A critical concern arises: what if biological conclusions, such as identifying a specific protein as a disease "hub," are merely artifacts of an arbitrary threshold choice? This paper by Bozhilova et al. introduces a rigorous framework to ensure that biological insights are robust and not just consequences of thresholding decisions.

The Challenge of Thresholding

Constructing a PIN involves a significant trade-off. Setting a low threshold results in a dense network that may be riddled with false positives. Conversely, a high threshold yields a sparse network that might exclude crucial biological signals. Because the topology of a PIN changes drastically as edges are added or removed, any node metric intended to serve as a proxy for biological importance must produce consistent rankings across a reasonable range of thresholds.

Figure 4: Impact of confidence score thresholds on network properties across different species. (A) Average degree and (B) average local clustering coefficient as a function of the threshold.

As demonstrated in Figure 4, fundamental network properties like average degree and local clustering are highly sensitive to the chosen threshold. If a metric's ranking of "important" proteins fluctuates wildly with minor threshold adjustments, its reliability for biological discovery is compromised. Until now, a formal method to quantify this "rank robustness" has been lacking.

Methodology: Defining Robustness

The authors developed a framework based on rank similarity, specifically targeting the top-ranking nodes that are most relevant to researchers. They introduced three key robustness measures:

  1. Rank Continuity: This measures the degree of change in top-node rankings between two very close thresholds (e.g., 0.40 vs 0.41).
  2. Rank Identifiability: This determines if a ranking at a single threshold can accurately represent the "average" ranking across an entire range of thresholds.
  3. Rank Instability: This calculates the total range of ranks a specific top-tier node occupies across the threshold range.

A significant part of their methodology involved LOUD (Leave-One-Out Difference) metrics. Unlike traditional metrics that look at a node's local properties, LOUD metrics measure the impact on a global network property—such as natural connectivity—when a specific node is removed.

Key Findings and the "Robust Four"

The study evaluated 25 different metrics across real-world PINs from the STRING and HitPredict databases, as well as synthetic networks. The results revealed that popularity does not equate to robustness.

The Failure of Common Metrics

Some of the most frequently used metrics in bioinformatics, including betweenness centrality and local clustering coefficients, were found to be among the least robust. Their rankings fluctuated significantly as network density changed, making them unreliable for threshold-dependent analyses.

The "Robust Four"

Four metrics consistently outperformed the others across all real-world datasets:

  • Number of edges in the step-1 ego network: A local metric focusing on a node and its immediate neighbors.
  • LOUD average redundancy: A measure of how much redundancy is lost when a node is removed.
  • LOUD number of edges in the step-1 ego network: The LOUD version of the ego network edge count.
  • LOUD natural connectivity: A measure of the network's structural robustness upon node removal.

These metrics tend to be more robust because they are less sensitive to distant changes in network topology compared to global metrics like betweenness.

Cross-Species Consistency and Stability

Despite biological differences, the robustness of these metrics was highly correlated across E. coli, yeast, and malaria parasites (Spearman correlations > 0.81). This suggests that the "Robust Four" are likely reliable across the tree of life. In the yeast network, for example, the "important" nodes identified by LOUD natural connectivity showed a 75% overlap between the 0.60 and 0.90 thresholds, whereas the overlap for the local clustering coefficient was less than 10%.

Conclusion and Future Directions

The research by Bozhilova et al. provides a vital tool for bioinformaticians. By identifying metrics that remain stable across thresholds, researchers can have greater confidence that their identified "hub" proteins are biologically significant rather than mathematical artifacts.

While calculating LOUD metrics can be computationally expensive—taking approximately 88 seconds per threshold for a yeast network of ~6,400 nodes—the gain in reliability is substantial. Future work may focus on optimizing these calculations for massive human interactomes and extending the robustness framework to other tasks like community detection and network alignment.

Summary updated

Abstract

Background Protein interaction databases often provide confidence scores for each recorded interaction based on the available experimental evidence. Protein interaction networks (PINs) are then built by thresholding on these scores, so that only interactions of sufficiently high quality are included. These networks are used to identify biologically relevant motifs or nodes using metrics such as degree or betweenness centrality. This type of analysis can be sensitive to the choice of threshold. If a node metric is to be useful for extracting biological signal, it should induce similar node rankings across PINs obtained at different reasonable confidence score thresholds. Results We propose three measures—rank continuity, identifiability, and instability—to evaluate how robust a node metric is to changes in the score threshold. We apply our measures to twenty-five metrics and identify four as the most robust: the number of edges in the step-1 ego network, as well as the leave-one-out differences in average redundancy, average number of edges in the step-1 ego network, and natural connectivity. Our measures show good agreement across PINs from different species and data sources. Analysis of synthetically generated scored networks shows that robustness results are context-specific, and depend both on network topology and on how scores are placed across network edges. Conclusion Due to the uncertainty associated with protein interaction detection, and therefore network structure, for PIN analysis to be reproducible, it should yield similar results across different confidence score thresholds. We demonstrate that while certain node metrics are robust with respect to threshold choice, this is not always the case. Promisingly, our results suggest that there are some metrics that are robust across networks constructed from different databases, and different scoring procedures.
BibTeX
@article{bozhilova2019measuring,
  author = {Lyuba V. Bozhilova and Alan Whitmore and Jonny Wray and Gesine Reinert and Charlotte M. Deane},
  title = {{Measuring rank robustness in scored protein interaction networks}},
  journal = {BMC Bioinformatics},
  year = {2019},
  doi = {10.1186/s12859-019-3036-6},
}
Figure