On the Robustness of Graph-Based Clustering to Random Network Alterations

Area of Science:

• Systems Biology
• Bioinformatics
• Network Science

Background:

• Biological functions arise from complex protein-protein interaction networks (interactomes).
• Identifying higher-order structures like protein complexes within interactomes is crucial.
• Existing graph-based clustering algorithms are widely used but sensitive to noise inherent in experimental data.

Purpose of the Study:

• To evaluate the robustness of graph-based clustering algorithms against noise in protein-protein interaction networks.
• To develop a method for quantifying cluster stability and reproducibility in the presence of network noise.

Main Methods:

• Tested various graph-based clustering algorithms on protein interaction networks with simulated noise.
• Developed and applied the clust.perturb R package and Shiny web application for network perturbation analysis.
• Correlated cluster reproducibility scores with experimental validation (reclustering across experiments).

Main Results:

• All tested clustering algorithms significantly amplified network noise, with minor edge changes causing substantial result alterations.
• Cluster robustness varied, with some clusters being consistently stable and others highly sensitive to noise.
• clust.perturb identified poorly reproducible clusters that were less likely to be validated in subsequent experiments.

Conclusions:

• Graph-based clustering methods amplify noise in protein interaction networks, potentially leading to spurious associations.
• Quantifying cluster robustness using methods like clust.perturb is essential for distinguishing stable protein complexes from noise.
• The clust.perturb tool aids in identifying reliable biological insights from noisy interactome data.