HipMCL: a high-performance parallel implementation of the Markov clustering algorithm for large-scale networks
Top Cited Papers
Open Access
- 5 January 2018
- journal article
- research article
- Published by Oxford University Press (OUP) in Nucleic Acids Research
- Vol. 46 (6) , e33
Abstract
Biological networks capture structural or functional properties of relevant entities such as molecules, proteins or genes. Characteristic examples are gene expression networks or protein–protein interaction networks, which hold information about functional affinities or structural similarities. Such networks have been expanding in size due to increasing scale and abundance of biological data. While various clustering algorithms have been proposed to find highly connected regions, Markov Clustering (MCL) has been one of the most successful approaches to cluster sequence similarity or expression networks. Despite its popularity, MCL’s scalability to cluster large datasets still remains a bottleneck due to high running times and memory demands. Here, we present High-performance MCL (HipMCL), a parallel implementation of the original MCL algorithm that can run on distributed-memory computers. We show that HipMCL can efficiently utilize 2000 compute nodes and cluster a network of ∼70 million nodes with ∼68 billion edges in ∼2.4 h. By exploiting distributed-memory environments, HipMCL clusters large-scale networks several orders of magnitude faster than MCL and enables clustering of even bigger networks. HipMCL is based on MPI and OpenMP and is freely available under a modified BSD license.Keywords
This publication has 50 references indexed in Scilit:
- Adaptive seeds tame genomic sequence comparisonGenome Research, 2011
- SPICi: a fast clustering algorithm for large biological networksBioinformatics, 2010
- jClust: a clustering and visualization toolboxBioinformatics, 2009
- Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein spaceBioinformatics, 2008
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Network biology: understanding the cell's functional organizationNature Reviews Genetics, 2004
- Cytoscape: A Software Environment for Integrated Models of Biomolecular Interaction NetworksGenome Research, 2003
- Detection of functional modules from protein interaction networksProteins: Structure, Function, and Bioinformatics, 2003
- Classification schemes for protein structure and functionNature Reviews Genetics, 2003
- An efficient algorithm for large-scale detection of protein familiesNucleic Acids Research, 2002