Finding local communities in protein networks

Abstract

Background: Protein-protein interactions (PPIs) play fundamental roles in nearly all biological processes, and provide major insights into the inner workings of cells. A vast amount of PPI data for various organisms is available from BioGRID and other sources. The identification of communities in PPI networks is of great interest because they often reveal previously unknown functional ties between proteins. A large number of global clustering algorithms have been applied to protein networks, where the entire network is partitioned into clusters. Here we take a different approach by looking for local communities in PPI networks.

Results: We develop a tool, named Local Protein Community Finder, which quickly finds a community close to a queried protein in any network available from BioGRID or specified by the user. Our tool uses two new local clustering algorithms Nibble and PageRank-Nibble, which look for a good cluster among the most popular destinations of a short random walk from the queried vertex. The quality of a cluster is determined by proportion of outgoing edges, known as conductance, which is a relative measure particularly useful in undersampled networks. We show that the two local clustering algorithms find communities that not only form excellent clusters, but are also likely to be biologically relevant functional components. We compare the performance of Nibble and PageRank-Nibble to other popular and effective graph partitioning algorithms, and show that they find better clusters in the graph. Moreover, Nibble and PageRank-Nibble find communities that are more functionally coherent.

Conclusion: The Local Protein Community Finder, accessible at http://xialab.bu.edu/resources/lpcf, allows the user to quickly find a high-quality community close to a queried protein in any network available from BioGRID or specified by the user. We show that the communities found by our tool form good clusters and are functionally coherent, making our application useful for biologists who wish to investigate functional modules that a particular protein is a part of.

Figure 1

Local Protein Community Finder user interface. The user selects a protein network from BioGRID (specified by an organism and a set of interaction types) and a query protein. In addition, the user can choose the size of the community and whether it must contain the starting protein.

Figure 2

Local Protein Community Finder output. An image of the found community is displayed, with the starting protein (if it is part of the community) shown in red, and the other proteins in the community shown in blue. A link to information about each protein is given at the top of the page. The user can also display the community in the protein interaction viewer VisANT by clicking on the link at the bottom of the page.

Figure 3

Average conductance of communities found by each algorithm. The algorithms compared are listed along the x-axis, the y-axis specifies the average conductance of communities found by each algorithm. Bars of different color are used to represent the results for the four protein networks in which the computational experiments are conducted. (a) The results for small clusters. (b) The results for medium clusters. (c) The results for large clusters.

Figure 4

Correlation between conductance and absolute/relative functional coherence in each network. The x-axis lists the protein networks. The y-axis gives the Pearson correlation coefficient for the correlation between conductance and functional coherence of protein groups in each network. Correlation between conductance and absolute functional coherence is shown in blue, and correlation between conductance and relative functional coherence is shown in red.

Figure 5

Average functional distance of interacting and non-interacting protein pairs in each network. The x-axis lists the protein networks. The y-axis displays the average functional distance of interacting (blue) and non-interacting protein pairs (red) in each network.

Figure 6

Average absolute functional coherence of communities found by each algorithm. The algorithms compared are listed along the x-axis, the y-axis specifies the average absolute functional coherence of communities found by each algorithm. Bars of different color are used to represent the results for the four protein networks in which the computational experiments are conducted. (a) The results for small clusters. (b) The results for medium clusters. (c) The results for large clusters.

Figure 7

Average relative functional coherence of communities found by each algorithm. The algorithms compared are listed along the x-axis, the y-axis specifies the average relative functional coherence of communities found by each algorithm. Bars of different color are used to represent the results for the four protein networks in which the computational experiments are conducted. (a) The results for small clusters. (b) The results for medium clusters. (c) The results for large clusters.