Global snapshot of a protein interaction network—a percolation based approach

Abstract

Motivation: Biologically significant information can be revealed by modeling large-scale protein interaction data using graph theory based network analysis techniques. However, the methods that are currently being used draw conclusions about the global features of the network from local connectivity data. A more systematic approach would be to define global quantities that measure (1) how strongly a protein ties with the other parts of the network and (2) how significantly an interaction contributes to the integrity of the network, and connect them with phenotype data from other sources. In this paper, we introduce such global connectivity measures and develop a stochastic algorithm based upon percolation in random graphs to compute them. Results: We show that, in terms of global connectivities, the distribution of essential proteins is distinct from the background. This observation highlights a fundamental difference between the essential and the non-essential proteins in the network. We also find that the interaction data obtained from different experimental methods such as immunoprecipitation and two-hybrid techniques contribute differently to network integrities. Such difference between different experimental methods can provide insight into the systematic bias present among these techniques. Supplementary information: The full list of our results can be found in the supplemental web site http://www.nas.nasa.gov/Groups/SciTech/nano/msamanta/projects/percolation/index.php