Geometric De-noising of Protein-Protein Interaction Networks

Understanding complex networks of protein-protein interactions (PPIs) is one of the foremost challenges of the post-genomic era. Due to the recent advances in experimental bio-technology, including yeast-2-hybrid (Y2H), tandem affinity purification (TAP) and other high-throughput methods for protein-protein interaction (PPI) detection, huge amounts of PPI network data are becoming available. Of major concern, however, are the levels of noise and incompleteness. For example, for Y2H screens, it is thought that the false positive rate could be as high as 64%, and the false negative rate may range from 43% to 71%. TAP experiments are believed to have comparable levels of noise.We present a novel technique to assess the confidence levels of interactions in PPI networks obtained from experimental studies. We use it for predicting new interactions and thus for guiding future biological experiments. This technique is the first to utilize currently the best fitting network model for PPI networks, geometric graphs. Our approach achieves specificity of 85% and sensitivity of 90%. We use it to assign confidence scores to physical protein-protein interactions in the human PPI network downloaded from BioGRID. Using our approach, we predict 251 interactions in the human PPI network, a statistically significant fraction of which correspond to protein pairs sharing common GO terms. Moreover, we validate a statistically significant portion of our predicted interactions in the HPRD database and the newer release of BioGRID. The data and Matlab code implementing the methods are freely available from the web site: http://www.kuchaev.com/Denoising.Author Summary: Proteins are responsible for much of the biological ‘heavy lifting’ that keeps our cells functioning. However, proteins don't usually work alone; instead they typically bind together to form geometrically and chemically complex structures that are tailored for a specific task. Experimental techniques allow us to detect whether two types of proteins are capable of binding together, or ‘interacting’. This creates a network where two proteins are connected if they have been seen to interact, just as we could regard two people as being connected if they are linked on Facebook. Such protein-protein interaction networks have been developed for several organisms, using a range of methods, all of which are subject to experimental errors. These network data reveal a fascinating and intricate pattern of connections. In particular, it is known that proteins can be arranged into a low-dimensional space, such as a three-dimensional cube, so that interacting proteins are close together. Our work shows that this structure can be exploited to assign confidence levels to recorded protein-protein interactions and predict new interactions that were overlooked experimentally. In tests, we predicted 251 new human protein-protein interactions, and through literature curation we independently validated a statistically significant number of them.