Fast algorithms for detecting overlapping functional modules in protein-protein interaction networks

Accumulating evidence suggests that biological systems are composed of interacting, separable, functional modules which is that groups of vertices within which connections are dense but between which they are sparse. Identifying these modules is likely to capture the biologically meaningful interactions. In recent years, many algorithms have been developed for detecting such structures. These algorithms however are computationally demanding, which limits their application. The existing deterministic methods used for large networks find separated modules, whereas most of the actual networks are made of highly overlapping cohesive groups of vertices. In this paper, we propose an iterative-clique percolation method (ICPM) for identifying overlapping modules in PPI (protein-protein interaction) networks. Our method is based on clique percolation method (CPM) which not only considers the degree of nodes to minimize the search space (The vertices in k-cliques must have the degree of k-1 at least), but also converts k-cliques to (k-1)-cliques. It uses (k-l)-cliques by appending one node to (k-1)-cliques for finding k-cliques. Furthermore, since the PPI network is noisy and still incomplete, some methods treat the PPI networks as weighted graphs in which each edge (e.g., interaction) is associated with a weight representing the probability or reliability of that interaction for preprocessing and purifying PPI data. Thus, we extend the ICPM into weighted networks which takes into account the link weights in a more delicate way by incorporating the subgraph intensity. We test our method on both computer-generated and PPI networks. Our analysis of the yeast PPI network suggests that most of these modules have well-supported biological significance in the context of protein localization, function annotation, protein complexes.