Spectral affinity in protein networks

Abstract

Background: Protein-protein interaction (PPI) networks enable us to better understand the functional organization of the proteome. We can learn a lot about a particular protein by querying its neighborhood in a PPI network to find proteins with similar function. A spectral approach that considers random walks between nodes of interest is particularly useful in evaluating closeness in PPI networks. Spectral measures of closeness are more robust to noise in the data and are more precise than simpler methods based on edge density and shortest path length.

Results: We develop a novel affinity measure for pairs of proteins in PPI networks, which uses personalized PageRank, a random walk based method used in context-sensitive search on the Web. Our measure of closeness, which we call PageRank Affinity, is proportional to the number of times the smaller-degree protein is visited in a random walk that restarts at the larger-degree protein. PageRank considers paths of all lengths in a network, therefore PageRank Affinity is a precise measure that is robust to noise in the data. PageRank Affinity is also provably related to cluster co-membership, making it a meaningful measure. In our experiments on protein networks we find that our measure is better at predicting co-complex membership and finding functionally related proteins than other commonly used measures of closeness. Moreover, our experiments indicate that PageRank Affinity is very resilient to noise in the network. In addition, based on our method we build a tool that quickly finds nodes closest to a queried protein in any protein network, and easily scales to much larger biological networks.

Conclusion: We define a meaningful way to assess the closeness of two proteins in a PPI network, and show that our closeness measure is more biologically significant than other commonly used methods. We also develop a tool, accessible at http://xialab.bu.edu/resources/pnns, that allows the user to quickly find nodes closest to a queried vertex in any protein network available from BioGRID or specified by the user.

Figure 1

A view of the protein complexes in one of the PPI networks. The AC-Western network, with proteins in the same complex labeled with the same color.

Figure 2

Which measure of closeness is best at predicting co-complex membership? The number of co-complex pairs (as a fraction of the total number of co-complex pairs in the network) among pairs in the top percentile of each closeness ranking is displayed. Higher values indicate measures that are more biologically meaningful. (a) The results for the AC-Western network. (b) The results for the AC-MS network. (c) The results for the Two-Hybrid network.

Figure 3

Which measure of closeness best correlates with functional distance? The average functional distance of pairs in the top percentile of each closeness ranking is displayed. Lower values indicate measures that are more biologically meaningful. (a) The results for the AC-Western network. (b) The results for the AC-MS network. (c) The results for the Two-Hybrid network. The average functional distance of two proteins in the genome is 5.8.

Figure 4

How robust is PageRank Affinity to noise? We add noise to a network represented by a graph G = (V, E) by randomly choosing r₁ * |E| of the true positive interactions and removing them, and randomly choosing r₂ * |E| of the true negative interactions and adding them. We calculate the robustness score of PageRank Affinity by computing the PageRank Affinity of each pair of vertices in the noisy network, and counting how often true positive interactions score higher than true negative interactions. As a base for comparison, we also compute the robustness score of shortest path closeness (with ties in distance broken randomly). (a) The results for r₁ = 0.1 and varying values of r₂. (b) The results for r₁ = 0.2 and varying values of r₂. (c) The results for r₁ = 0.3 and varying values of r₂. (d) The results for r₁ = 0.4 and varying values of r₂.