Title: A hybrid graph-theoretic method for mining overlapping functional modules in large sparse protein interaction networks

Authors: Shihua Zhang, Hong-Wei Liu, Xue-Mei Ning, Xiang-Sun Zhang

Addresses: Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; Graduate University of Chinese Academy of Sciences, Beijing 100049, China. ' Beijing Wuzi University, Beijing 101149, China. ' College of Science, Beijing Forestry University, Beijing 100083, China. ' Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

Abstract: Modular architecture, which encompasses groups of genes/proteins involved in elementary biological functional units, is a basic form of the organisation of interacting proteins. Here, we propose a method that combines the Line Graph Transformation (LGT) and clique percolation-clustering algorithm to detect network modules, which may overlap each other in large sparse PPI networks. The resulting modules by the present method show a high coverage among yeast, fly, and worm PPI networks, respectively. Our analysis of the yeast PPI network suggests that most of these modules have well-biological significance in context of protein localisation, function annotation, and protein complexes.

Keywords: large sparse PPI networks; protein–protein interactions; network clustering; LGT; line graph transformation; protein complexes; overlapping functional modules; data mining; bioinformatics; graph theory; genes; proteins; protein localisation; function annotation.

DOI: 10.1504/IJDMB.2009.023885

International Journal of Data Mining and Bioinformatics, 2009 Vol.3 No.1, pp.68 - 84

Published online: 17 Mar 2009 *

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