Discovering overlapping modules and bridge proteins in proteomic networks

We describe a novel algorithm for identifying the modular structure of a protein interaction network by computing overlapping clusters. The network is initially decomposed into a high degree network and a residual subnetwork, and clusters are computed separately in both networks, before highly interconnected clusters in both networks are merged. We propose the concept of bridge proteins, proteins that are connected to multiple clusters, and identify them from the clustering. We show that bridge proteins are more likely to be essential. The clustering algorithm is used to identify modules in a collection of proteomic networks from the yeast, human, and the worm. The new algorithm is efficient at detecting both overlapping clusters and bridge proteins, and performs better than earlier algorithms in various measures of clustering quality.