PS-MCL: parallel shotgun coarsened Markov clustering of protein interaction networks

Yongsub Lim, In-Jae Yu, Dongmin Seo, U Kang, Lee SaelBMC Bioinformatics 2019 · DOI · OpenReview

Abstract

Identifying functional modules and protein complexes within large-scale biological networks is a fundamental task in bioinformatics. While Markov Clustering (MCL) is a widely adopted method, it frequently suffers from a "fragmentation problem," where networks are partitioned into numerous biologically insignificant tiny clusters. This paper presents PS-MCL (Parallel Shotgun Coarsened MCL), an algorithm that introduces a novel "shotgun" approach to graph coarsening. By allowing multiple nodes to merge into super-nodes simultaneously and leveraging multi-core parallelization, PS-MCL effectively eliminates fragmentation, improves clustering accuracy by up to 33.2%, and reduces runtime compared to existing multi-level methods.

Introduction

Graph clustering is essential for uncovering the organizational principles of protein-protein interaction (PPI) networks. The Markov Clustering (MCL) algorithm, which simulates random walks to identify dense regions, has long been a gold standard. However, MCL often produces a skewed distribution of cluster sizes, resulting in thousands of clusters containing only 1-3 nodes. This fragmentation misses the mid-sized complexes (5-20 nodes) that are typically most relevant to biological function.

Previous attempts to mitigate this, such as Multi-level Regularized MCL (MLR-MCL), utilized Heavy Edge Matching (HEM) to simplify graphs before clustering. However, HEM is restricted to one-to-one node merges, making it inefficient for "power-law" networks where hubs connect to many peripheral nodes. In such cases, HEM can inadvertently merge nodes across functional boundaries, leading to poor cluster quality or continued fragmentation.

Methods

PS-MCL introduces two primary innovations to address these challenges: Shotgun Coarsening (SC) and Multi-Core Parallelization.

Shotgun Coarsening (SC)

Unlike the greedy pair-matching of HEM, Shotgun Coarsening allows multiple "satellite" nodes to merge into a single "center" node in a single step. This approach more accurately reflects the star-like topologies common in biological networks. By grouping these satellites into a single super-node, the algorithm preserves local density and reduces the graph size more rapidly without the topological distortions introduced by HEM.

Comparison of coarsening strategies: (a) Ideal clustering, (b) Coarsening in progress, (c) HEM merging bridge nodes, and (d) Proposed SC preserving cluster structure.

Multi-Core Parallelization

To handle massive datasets, PS-MCL parallelizes the core matrix operations of the MCL process: Regularize, Inflate, and Prune. The algorithm utilizes a Compressed Sparse Column (CSC) format, which treats matrix-matrix multiplication as independent matrix-vector operations. This allows the workload to be distributed efficiently across multiple CPU cores while minimizing memory overhead by ignoring zero-value entries in sparse biological matrices.

Key Results

The performance of PS-MCL was evaluated across 11 diverse datasets, including BioPlex, MINT, and Drosophila PPI networks.

Solving the Fragmentation Problem

A critical achievement of PS-MCL is the significant reduction of tiny clusters. By employing a "balancing factor" (b) to penalize excessive flow to high-degree nodes, the algorithm shifts the cluster size distribution toward the biologically relevant 5–20 node range.

Cluster size distributions across multiple datasets. PS-MCL (blue) consistently reduces the number of tiny clusters (size 1-3) compared to standard MCL (black) and MLR-MCL (red).

Accuracy and Efficiency

In benchmarks against known protein complexes (CYC2008 and CORUM), PS-MCL demonstrated up to 33.2% higher accuracy than standard MCL. Furthermore, the algorithm is computationally efficient, outperforming MLR-MCL by 21% on average. Scalability tests on the large-scale DBLP dataset showed a 55% reduction in runtime when moving from one core to four cores.

Conclusion

PS-MCL represents a significant advancement in biological network clustering. By combining a topologically-aware coarsening strategy with efficient parallelization, it overcomes the long-standing fragmentation problem of MCL. While the algorithm is sensitive to certain parameters like the "skip rate," its ability to produce high-quality, biologically meaningful clusters makes it a powerful tool for functional module detection and gene function prediction.

Summary updated

Abstract

How can we obtain fast and high-quality clusters in genome scale bio-networks? Graph clustering is a powerful tool applied on bio-networks to solve various biological problems such as protein complexes detection, disease module detection, and gene function prediction. Especially, MCL (Markov Clustering) has been spotlighted due to its superior performance on bio-networks. MCL, however, is skewed towards finding a large number of very small clusters (size 1-3) and fails to detect many larger clusters (size 10+). To resolve this fragmentation problem, MLR-MCL (Multi-level Regularized MCL) has been developed. MLR-MCL still suffers from the fragmentation and, in cases, unrealistically large clusters are generated. In this paper, we propose PS-MCL (Parallel Shotgun Coarsened MCL), a parallel graph clustering method outperforming MLR-MCL in terms of running time and cluster quality. PS-MCL adopts an efficient coarsening scheme, called SC (Shotgun Coarsening), to improve graph coarsening in MLR-MCL. SC allows merging multiple nodes at a time, which leads to improvement in quality, time and space usage. Also, PS-MCL parallelizes main operations used in MLR-MCL which includes matrix multiplication. Experiments show that PS-MCL dramatically alleviates the fragmentation problem, and outperforms MLR-MCL in quality and running time. We also show that the running time of PS-MCL is effectively reduced with parallelization.
BibTeX
@article{lim2019ps,
  author = {Yongsub Lim and In-Jae Yu and Dongmin Seo and U Kang and Lee Sael},
  title = {{PS-MCL: parallel shotgun coarsened Markov clustering of protein interaction networks}},
  journal = {BMC Bioinformatics},
  year = {2019},
  doi = {10.1186/s12859-019-2856-8},
}
Figure