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.
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.
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