Title: A parallel edge-betweenness clustering tool for Protein-Protein Interaction networks

Authors: Qiaofeng Yang, Stefano Lonardi

Addresses: Department of Computer Science and Engineering, University of California, Riverside, CA 92521, USA. ' Department of Computer Science and Engineering, University of California, Riverside, CA 92521, USA

Abstract: The increasing availability of protein-protein interaction graphs (PPI) requires new efficient tools capable of extracting valuable biological knowledge from these networks. Among the wide range of clustering algorithms, Girvan and Newman|s edge betweenness algorithm showed remarkable performances in discovering clustering structures in several real-world networks. Unfortunately, their algorithm suffers from high computational cost and it is impractical for inputs of the size of large PPI networks. Here we report on a novel parallel implementation of Girvan and Newman|s clustering algorithm that achieves almost linear speed-up for up to 32 processors. The tool is available in the public domain from the authors| website.

Keywords: system biology; protein-protein interaction networks; PPI; graph clustering; distributed tools; data mining; bioinformatics; parallel edge betweenness; clustering structures.

DOI: 10.1504/IJDMB.2007.011611

International Journal of Data Mining and Bioinformatics, 2007 Vol.1 No.3, pp.241 - 247

Published online: 06 Dec 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article