BACKGROUND
protein-protein interactions  are essential molecular interactions that define the biology of a cell, its development and responses to various stimuli.
physical interactions between proteins can form the basis for protein functions, communications, and regulation and controls within a cell.
such interactions can result in the formation of protein complexes that perform specific tasks.
similarly, internal and external signals are often realized and communicated through the formation of stable or transient ppis.
due to their central importance to the integrity of communication networks within a cell, ppis are thought to involve important targets for drug discovery  <cit>  and are linked to a number of cellular conditions and diseases  <cit> .
our current knowledge of global ppi networks in different organisms is hindered by the constraints and limitations of existing experimental techniques amenable to high throughput ppi studies, such as yeast-two-hybrid  and affinity purification combined with mass spectrometry .
while both of these techniques have been successfully applied to global ppi detection in the yeast, saccharomyces cerevisiae  <cit> , they suffer from significant shortcomings highlighted by the lack of overlap observed between the ppi data in different reports.
the two benchmark large-scale yeast apms investigations have less than 25% overlap and this overlap is even less for the two classic y2h projects  <cit> .
only  <dig> ppis are shared between all four studies, further highlighting the gap in our understanding of global ppi networks.
although recent technical improvements are expected to increase the confidence of the detected ppis and hence fill some of the current gap of knowledge, increasing the coverage and quality of ppi networks remains an important challenge  <cit> .
computational tools offer time and cost effective alternatives to traditional wet-lab ppi detection tools.
they may also be used as “filters” to increase confidence in data derived from wet-lab experiments  <cit> .
like other techniques, most computational tools also suffer from notable deficiencies.
for example, most computational methods rely heavily on previously reported data.
assuming that there are inherent discrepancies in the training data, the accuracies of such tools to detect new interactions are often questionable.
moreover, novel interaction domains or motifs are likely to be missed by methods that rely heavily on the structures or other high-level features of protein pairs known to interact.
another major shortcoming of computational tools is that they are often too computationally intensive, making them impossible to use for proteome-wide analysis.
to date, no comprehensive all-against-all analysis of the entire human ppi network has been possible.
a small number of large-scale computational ppi prediction methods have recently been published .
although these methods have provided important contributions to the field, they are not applicable to the entire human proteome due to computational complexity, availability of input protein features, or unacceptably high false positive rates.
for example, a recent study by elefsinioti et al.
examined five million protein pairs and predicted  <dig>  “high confidence” interactions  <cit> .
given a conservative estimate of  <dig>  human proteins, leading to  <dig> million possible pairs, elefsinioti et al.
have examined only 2% of the potential interactome while others have examined just over 7%  <cit>  and  <dig> %  <cit>  of the total interactome.
presumably these methods were limited to examining only small subsets of protein pairs due to computational complexity  or the availability of input protein features.
for example, the method of elefsinioti et al.
<cit>  requires  <dig> complex features for each protein relating to annotated function, sequence-derived attributes, and network structure.
likewise, the method of zhang et al.
<cit>  requires structural information for both proteins in the putative interaction and is therefore only applicable to  <dig>  human proteins .
when considering protein pairs rather than individual proteins, approximately 50% sequence coverage results in an examination of at most 25% of the possible ppis.
in fact, zhang et al.
report that they were able to develop models for  <dig> million interactions, representing  <dig> % of the  <dig> million possible interactions.
even if these methods could be applied to all human protein pairs, typical false positive rates will render existing methods unusable on larger data sets.
for example, considering that the method of elefsinioti et al.
<cit>  predicts  <dig>  “high confidence” interactions among only  <dig> % of protein pairs, then we can reasonably expect nearly  <dig> million “high confidence” predicted interactions if their method were to be applied to the entire human proteome.
this is an order of magnitude higher than the largest current estimate of the true size of the human interactome  <cit> , leaving the experimenter to weed through a multitude of false positive predictions to find the few true interactions.
likewise, using a previously published computational method  <cit> , zhang et al.
recently reported  <cit>  a false positive rate implying  <dig> % precision, and their recall over an independent test set of  <dig>  newly reported ppis is less than 7%.
consequently, there is a need for the development of efficient tools that are readily amenable to proteome-scale ppi prediction.
this is especially important as the field of personalized medicine will benefit tremendously from a fast and accurate method that can predict the global ppi maps of different individuals from their genomic sequences alone.
a subset of cellular ppis is mediated by defined short, linear polypeptide sequences  <cit> .
leveraging this fact, a number of computational tools have been developed to detect ppis solely on the basis of primary sequence  <cit> .
such approaches do not rely on known structures or other protein features that are not easily deduced from primary protein sequences, and are thus, in principle, able to interrogate portions of the proteome that are inaccessible to other methods.
some of their predictions have been confirmed by tandem affinity purification  <cit> , in vitro binding assays  <cit> , and in vivo functional analysis  <cit> .
an added benefit of sequence-based ppi prediction is that short polypeptide sequences in one organism can be used to predict ppis in another  <cit> .
we note that, while the wide applicability of sequence-based ppi prediction methods is clearly a strength, in not using structural predictions, such techniques may be unable to account for structural features such as binding site accessibility or widespread contacts between non-contiguous residues.
we have developed a computational tool termed the protein interaction prediction engine  that uses co-occurrence of short polypeptide regions to detect novel ppis in s. cerevisiae  <cit> .
although pipe was able to analyze potential ppis within certain proteomes, applying this tool to more complex proteomes remained infeasible due to computational complexity.
analyzing the ~ <dig> million protein pairs in the human proteome was estimated to require approximately  <dig>  million cpu-hours of computation.
in order to study the human ppi network, we developed a new massively parallel  version of pipe, which we call mp-pipe.
mp-pipe overcomes some of the limitations of existing methods through computational acceleration of the algorithm  and improved precision.
we present a comprehensive all-against-all  analysis of the human proteome and study its biological properties.
we then demonstrate the accuracy and utility of the mp-pipe inferred interactome using a range of functional assays.
RESULTS
mp-pipe performance and scalability enables computational scan of entire human proteome
one of the main issues when predicting human protein interactions on a large scale, which does not occur for simpler organisms such as s. cervisiae or c. elegans, is the complexity of the human proteome.
more precisely, when predicting human protein interactions using previous methods  <cit> , the compute time to process a single human protein pair can vary between several seconds and more than 12 hours.
this effect has so far only been observed for the human protein interactions.
our previous method  <cit>  was ranked highly in terms of prediction accuracy in an independent comparison study  <cit> .
however, it would be unable to process all human protein pairs in our lifetime .
therefore, we developed an algorithm called mp-pipe, capable of performing global ppi analysis of the human proteome.
although the task of performing a proteome-wide, all-to-all prediction within the human proteome is still extremely computationally expensive for mp-pipe, it still remained a feasible task and was completed within three months though massive parallelization.
from a computer science perspective, the main challenge is the massive load imbalance of the parallelization.
as shown in figure 1a, for the vast majority of protein pairs, protein interaction prediction can be performed in seconds.
however, for some protein pairs, the process takes minutes or hours, more than 12 hours in  <dig>  extreme cases.
solving this load imbalance in an efficient manner is the main computational contribution of mp-pipe.figure  <dig>
mp-pipe benchmark performance.
a) distribution of running times for human protein-protein interaction prediction.
numbers above bars indicate approximate number of protein pairs with a running time within the given range.
b) performance for different numbers of threads per worker on the large cluster.
average running times for  <dig>  random protein pairs  or  <dig>  random protein pairs , using one worker process.
c) performance for different numbers of workers on the large cluster.
average running times for  <dig>  random protein pairs, using  <dig> threads per worker.
in the following, we discuss the runtime performance of mp-pipe on different hardware architectures which eventually enabled us to perform global ppi analysis of a human cell within three months.
more precisely, we tested our mp-pipe solution on three different compute clusters.
these clusters included a six node cluster with  <dig> total compute cores , a  <dig> node cluster with  <dig> total compute cores , and a  <dig> node cluster with  <dig>  total hardware supported threads .
the performance of mp-pipe was initially tested on a single large cluster node with varying numbers of threads, and then in a second test we increased the number of nodes .
the test data set consisted of  <dig>  random protein pairs.
however, this data set proved to be too large to compute using a small number of threads, so a subset containing  <dig>  random pairs was used to examine the runtime performance of the code with 1– <dig> threads and then the full  <dig>  pair data set was used for tests with  <dig> or more threads.
for those test cases that were performed over the smaller  <dig>  pair subset, runtimes were extrapolated to estimate the runtime over the full  <dig>  pair dataset.
the results are shown in figure  <dig>  the speedup curve shown in figure 1b shows a dramatic performance improvement using up to  <dig> threads and then a slight improvement from there up to  <dig> threads.
we found that using more than  <dig> threads creates memory problems.
for the second test, we increased the number of large cluster nodes used, where each node ran one mp-pipe worker with  <dig> worker threads.
the results are shown in figure 1c.
the performance of mp-pipe scales almost linearly as the number of compute nodes increases.
this scalability property of mp-pipe enabled us to perform global ppi analysis of the human proteome within three months.
verification of mp-pipe against experimental data
as with other ppi prediction methods, mp-pipe relies on previously reported interaction data to make its predictions.
the quality of the predictions made is inherently determined on the quality of this input data.
to determine the prediction accuracy of mp-pipe for human ppis we conducted a leave-one-out  test of mp-pipe using the  <dig>  experimentally verified, high-confidence human ppis taken from biogrid and  <dig>  randomly chosen negative protein pairs .
choosing negative data in this way avoids sources of bias introduced by other methods .
the loo tests were conducted as follows: mp-pipe was run  <dig>  times, one for each experimentally verified interacting protein pair .
for each test run , we removed the known interaction  from the database.
in this manner, we create a state where mp-pipe is not aware of the experimentally verified ppi , as if that interaction had not been measured yet.
we then asked mp-pipe to predict whether or not proteins a and b interact.
the same was then done for the negative set of randomly selected protein pairs that were expected to not interact.
once finished, the  <dig>  total mp-pipe predictions made were sorted by their pipe score.
examining this sorted list allows us to set our decision threshold operating point.
given any “accept threshold” , we can then see how many false positives and negatives were produced during our  <dig>  test runs.
given the expected ratio of  <dig> non-interacting protein pairs for each interacting protein pair, typically a threshold that achieves an extremely high specificity  is chosen in order to minimize out false positive rate.
at the chosen operating point, mp-pipe produced  <dig>  true positives ,  <dig>  true negatives ,  <dig> false positives  and  <dig>  false negatives  from the  <dig>  total test predictions made.
these results are summarized in the confusion matrix in table  <dig> table  <dig>
confusion matrix for the leave-one-out cross-validation tests used to determine the prediction accuracy of mp-pipe
known interacting pairs
assumed non-interacting pairs
total
predicted to interact
predicted not to interact
total
since the ratio of known interacting pairs to assumed non-interacting pairs in our test set  is not representative of the true ratio expected among all protein pairs within the h. sapiens proteome, the results in the above confusion matrix require adjustment.
this adjustment to account for the true prevalence of ppis among all protein pairs leads to a more conservative and realistic estimate of predictive performance of mp-pipe.
we have used a ratio of  <dig> non-interacting protein pairs per interacting pair.
we feel this is a more realistic estimate given the expected sparsity of the actual interaction network and the range of estimates reported in previous studies  <cit> .
the ratio-adjusted confusion matrix adjusted for this ratio is shown in table  <dig> table  <dig>
the ratio-adjusted confusion matrix the leave-one-out cross-validation tests used to determine the prediction accuracy of mp-pipe
known interacting pairs
assumed non-interacting pairs
total
predicted to interact
predicted not to interact
total
a wide variety of performance metrics are commonly used to assess ppi prediction methods.
these are summarized and computed in table  <dig> below.table  <dig>
statistical performance metrics for mp-pipe based on true negatives , true positives , false negatives , and false positives  seen in the leave-one-out cross-validation tests, corrected to use a positive: negative ratio of 1:100
statistical measure
definition
value
tnfp+tn
tptp+fn
tptp+fp
tp+tntp+fp+fn+tn
2tp2tp+fp+fn
tpxtn−fpxfntp+fptp+fntn+fptn+fn
this leave-one-out test was repeated with all homologs removed from our human dataset as in  <cit> .
this reduced our protein sequence set from  <dig>  to  <dig>  and our experimentally verified human ppi set from  <dig>  to  <dig>  pairs.
removing homologs at the 40% identity level effectively removes all protein isoforms from our loo performance assessment.
this leads to a conservative estimate of performance as not removing the homologs could potentially inflate the reported statistical performance figures  <cit> .
as can be seen in the figure in additional file  <dig> , the recall of our method is slightly reduced when homologous proteins are removed from our dataset, however if we adjust our decision threshold to maintain a recall of 23%, we still achieve a precision of  <dig> %.
all-against-all  scan of the human proteome
after three months of 24/ <dig> computation on the  <dig> fully dedicated nodes of the large cluster , mp-pipe completed the scan of the human proteome.
with the chosen operating point as described in the previous section, mp-pipe predicted  <dig>  protein interactions.
of these high confidence predictions,  <dig>  protein interactions have never been reported previously.
given that  <dig>  human protein interactions are known  and were included in the mp-pipe database and would therefore be predicted to interact, mp-pipe has potentially more than quadrupled our knowledge of the human interaction network.
at the chosen operating point, mp-pipe data covers more than one fifth of the estimated human ppi landscape.
in comparison, elefsinioti et al.
<cit>  have examined 2% of the interactome while others have examined just over 7%  <cit>  and  <dig> %  <cit>  of the total interactome.
the list of the reported interactions is found in the table in additional file  <dig>  the list is ordered according to pipe score, where higher values represent higher confidence levels for an interaction.
distribution of run time for different human protein pairs is illustrated in figure 1a.
the length of the query proteins does not appear to correlate with runtime .
the analysis performed on mp-pipe’s predicted  <dig>  interactions throughout the rest of this study will cover both the known  <dig>  and novel  <dig>  interactions, unless stated otherwise.
besides leave one out cross-validation, another standard method for evaluating ppis is to check whether the proteins pairs predicted to interact are co-located within the same cellular component, have the same molecular function, are involved in the same biological process or have a common third party interacting partner.
the results of this analysis are shown in table  <dig> and figure  <dig>  the overall profiles for the predicted interacting pairs that have not been detected before, on the basis of cellular localization, process and function resembles that of previously reported pairs .
certain differences however are noticeable.
for example, a new association for “metal ion binding” and “transcription” is observed for the predicted interactions and not for those that have been previously reported .
similarly, there is a strong association between “immune response” and “signal transduction” for the predicted interactions .
as indicated in table  <dig>  the percentage of predicted interacting protein pairs that have similar function, occur in the same cellular component and participate in the same cellular process is  <dig> %, which is consistent with the percentage for previously reported protein pairs .
in contrast, only  <dig> % of randomly selected protein pairs share these three traits.
it is important to note that the pipe algorithm has no previous knowledge of the protein location, molecular function of proteins, or the biological processes in which they are involved.
such an association for protein pairs predicted by mp-pipe further highlights the ability of this method to predict interactions that can be supported by independent parameters.
such contextual information can also be used to assign an independent degree of confidence for ppi predictions.
for example, higher confidence might be assumed for a protein pair where both proteins occur in the same location and share the same go term for a cellular process.
this information is presented in the table in additional file  <dig> and can be used to form a priority list of interactions for further biological analysis.table  <dig>
percentages of
homo sapiens
pairs in which both partners share the same go slim annotation as well as third party interactions
derived from go annotation
third party interaction
cellular component
molecular function
biological process
cc & mf & bp
*p-value <1e- <dig>
distribution of the interacting protein pairs on the basis of subcellular localization , molecular function  and cellular process  for both previously detected interactions and interactions unique to this study normalized by the number of possible pairs with both go terms.
the overall co-occurrence  for pairs that were previously not reported is similar to that of previously reported interactions.
the observed enrichment for certain categories within predicted interactions may represent new association or cross-communication.
for example, in panel b, a co-occurrence  for “metal ion binding” and “transcription” is observed for predictions that were not previously reported.
similarly, in panel c, “immune response” and “signal transduction” have a more profound association among the predicted interacting pairs in this study.
in addition to the above cross-validation, we independently evaluated the competence of our predictions by evaluating experimental data gathered using the lentivirus-delivered, gateway-compatible affinity tagging system coupled with mass spectrometry  approach that has been recently developed for the identification of ppis in mammalian cell lines  <cit> .
the lgts system uses a versatile affinity -tag constructed in-frame with a gateway cassette consisting of 3x flag, 6x his, and 2x streptactin  epitopes, with flag and his separated by dual tev protease cleavage sites for efficient affinity purification  <cit> .
using this approach, we stably expressed four , rnf <dig> , h2afx , and rbbp <dig> ) c-terminal affinity tagged chromatin-related proteins in human embryonic kidney   <dig> cells that play an important role in the epigenetic control of chromatin structure and gene expression, transcriptional repression, nucleosome remodeling, and chromatin assembly  <cit>  .
these tagged proteins were affinity-purified in one step on anti-flag resins and the interacting proteins were identified by tandem mass spectrometry.figure  <dig>
affinity purification experiments using p <dig> , q <dig> , p <dig> , and q <dig>  as baits.
immunoblot confirming the expression of the indicated flag-tagged chromatin proteins using antibody against the 3x flag epitope.
two independent flag tag constructs of each chromatin related protein was constructed for affinity purifications to eliminate background contaminants and to uncover highly reproducible interactions.
molecular masses  of marker proteins by sds-page are indicated.
representative functional clusters identified from affinity purification data  and expanded by mp-pipe predictions .
tagged-baits are shown by yellow nodes .
blue nodes represent co-purifying proteins identified through affinity purification.
purple nodes represent proteins added to the functional clusters through mp-pipe predictions.
red dashed edges  represent previously reported binary interactions identified in literature experimental data and green solid edges represent novel  mp-pipe binary interaction predictions.
as expected, we recovered both the bait and several well-known interacting protein partners, such as the interaction between the tagged histone binding protein, rbbp <dig>  and subunits of the core histone deacetylase complex  and rbbp <dig> ), confirming the overall efficacy of the protein purification procedure employed in the identification of co-purifying interacting proteins .
consistent with the biological expectation, these co-purifying proteins were enriched for more chromatin related functions such as chromatin organization, binding and assembly; nucleosome assembly; histone ubiquitination; and transcriptional regulation.
examples of functional clusters identified through the lgts-ms based method are shown in figure 3b.
to investigate mp-pipe’s ability to explain the observed lgts-ms data, we computed the precision and recall of mp-pipe predicted interactions.
this is summarized in table  <dig> where reachable proteins are defined as those proteins that interact directly or through one or two intermediary proteins.
this accounts for the fact that a bait and prey observed to co-purify in a lgts-ms experiment may, in fact, interact indirectly through one or more intermediary proteins.
for the four baits, previously known ppi interactions  can only explain on average  <dig> %  of the co-purifying proteins .
using mp-pipe predictions increases our recall by ~3-fold  while maintaining comparable precisions.table  <dig>
overlap of co-purifying proteins identified through lgts-ms with previously reported  interactions and mp-pipe predictions
reachable proteins
prey reached
recall
1
precision
2
bait
# of prey
known
mp-pipe
known
mp-pipe
known
mp-pipe
known
mp-pipe
total
1276
258
676
139
374
<dig> %
<dig> %
<dig> %
<dig> %
1recall calculated as reached/# of prey.
2precision calculated as reached/reachable.
our predicted interactions appear to have a wide coverage of the human proteome.
for instance, of the  <dig>  human potential open reading frames included in this study,  <dig>  were found in our prediction list  for a coverage of approximately 50%.
since a total of  <dig>  interactions were predicted, on average there appears to be approximately  <dig> interactions for each protein found in the prediction list.
as illustrated in figure  <dig>  approximately 32% of the predicted interactions occur in the nucleus, followed by 21% in the cytoplasm.
in fact, the distribution of the identified interactions is very consistent with those of the previously reported  ones.
this distribution is also in accordance with the previously reported ppi distribution in s. cerevisiae  <cit> .
of interest are membrane proteins, which although not readily amenable to experimental assays, received good coverage using mp-pipe.
the full range of biological processes and molecular functions is also well covered .
on the basis of expression level ,  <dig> % and  <dig> % of highly and low expressed proteins, respectively, also appear in the list of ppis.
we also examined the interactions for fibroblast growth factors  and cyclin-dependent kinases  with fibroblast growth factor receptors  and regulatory inhibitors and activators of cyclin-dependent kinases, respectively.
these represent examples of proteins that share high similarity in primary sequence and molecular function, yet have differences in substrate specificity and regulatory factors.
shown in the table in additional file  <dig> there are clear differences in interacting partners for different members of fgf and cdk proteins.
altogether these observations suggest that our prediction method appears to be inclusive and specific, and is amenable to diverse set of proteins presenting a good coverage of the proteome.figure  <dig>
number  and percentage  of co-localized interacting pairs by go components in previously reported data compared with those reported in this study only.
note that since proteins can have multiple tags, interacting pairs can be co-localized in several components and can be counted more than once.
network-wide analysis of hubs and betweenness centrality
in a ppi network, the degree of interaction for a target protein is believed to be a good indicator for the biological importance of that protein within the system  <cit> .
removal of the highly connected proteins or “hubs” appears to have a more profound effect on the integrity of the network by reducing the size of the largest connected module, than removal of random proteins  <cit> .
we studied the top  <dig>   <dig> and  <dig> hubs with the highest number of interactions within our predicted ppi network, and observed very high enrichment for proteins that affect transcription and gene expression .
transcription factors mediate differential genetic programming and hence are of central importance in developmental biology  <cit> , responses to stimuli  <cit> , disease progression  <cit> , etc.
betweenness centrality is another topological feature of a network and evaluates the number of shortest paths that pass through a given node  <cit> .
therefore, high betweenness centrality for a protein represents the relative number of shortest paths that are associated with that protein.
consequently, proteins with high betweenness centrality are thought to play a central role in the cross-talk and communication between interconnected modules of a network by forming “traffic bottlenecks” for communication  <cit> .
we evaluated the top  <dig>   <dig> and  <dig> proteins with highest betweenness centrality values within our predicted network.
consistent with the expected role of these proteins in signaling, we observed  that they were highly enriched for proteins involved in intracellular communication , or for which communication is of central importance .table  <dig>
enrichment of biological process for proteins with highest hub degree  or betweeness centrality  measurements
biological process
top 10
top 25
top 50
# prot
p-value
# prot
p-value
# prot
p-value
hubs
transcription regulation
regulation of gene expression
b.c.
protein kinase activity
regulation of cell death
signaling
centrality measurements are often used to predict the possible involvement of a protein in disease etiology and progression.
some studies suggest that hubs are likely enriched for disease proteins, whereas others incline towards betweenness centrality as a better indicator  <cit> .
we therefore examined a possible relationship between the top  <dig> proteins with the highest degrees of centrality  and their reported involvement in disease progression.
as illustrated in figure  <dig>  both hub and betweenness centralities appear to be good indicators for disease proteins.
however, betweenness centrality appeared to have a better correlation than hubs for disease proteins.
a ranked list of top  <dig> proteins according to their centrality measures is reported in additional file  <dig>  and the table in additional file  <dig> .
we note that the relationship between connectivity  and disease is dependent on a variety of factors, particularly gene essentiality  <cit> , which we have not investigated here in depth.figure  <dig>
comparing the number of disease-associated proteins with high degree  and high betweenness centrality.
proteins with highest betweenness centrality appear to be more enriched for disease proteins than hubs.
the usefulness of the predicted interactions in biological investigations
our computationally predicted interactome represents a comprehensive all-to-all interaction network in humans.
this network generates a wide range of testable hypotheses concerning biological processes, and informs our understanding of the overall architecture of cellular function.
here, we demonstrate the usefulness of this new predicted interactome through prediction of gene functions, experimental verifications and analysis of putative protein complexes.
using the predicted human protein interaction network to assign breast cancer proteins
breast cancer is the most commonly diagnosed form of cancer among women  <cit> .
brca <dig> and to some extent brca <dig> are the two key genes associated with breast cancer progression.
breast cancer susceptibility has been related to a mutation of brca <dig>  <cit> .
carriers of brca <dig>  mutations have a 50-80% increased risk of developing breast cancer  <cit> .
it is estimated that 10% of western women fall in this category  <cit> .
while the tumor suppression property of brca <dig> is well investigated, the molecular mechanism of its activity in tumor prevention is not fully understood  <cit> .
figure  <dig> illustrates a brief overview of the breast cancer pathway where brca <dig> plays a central role.
as illustrated,  brca <dig> is directly associated with several cellular processes including chromatin remodeling, dna damage checkpoint activation, dna damage sensing, and dna double stranded break  repair.
brca <dig> plays an essential role in delaying cell cycle progression by its dna damage checkpoint activity.
atm phosphorylation of p <dig>  a tumor suppressor protein, is mediated by brca <dig> and, in the presence of dna damage, delays or arrests g1/s transition  <cit> .
brca <dig> is important during s phase and g2/m checkpoint activation through its regulation of kinase activity of chk <dig>  <cit> .
upon dna damage, h2ax is phosphorylated by atm and atr and recruits mdc and rnf <dig> to the site of the damage.
subsequently, brca <dig> is translocated to the site of damage by ubiquitination of h2a through rnf <dig> and ubc <dig>  <cit>  and interacts with the mre11/rad50/nbs  complex that is involved in double stranded dna break repair  <cit> .
examining the proteins involved in the breast cancer pathway for ppis, mp-pipe predicted over  <dig>  interactions,  <dig> of which  directly involve brca <dig> .
studying these interactions can expand our current understanding of the breast cancer pathway.
a number of interesting factors were found to form novel interactions with multiple proteins associated with the breast cancer pathway, including cdk <dig>  aurkb, and smc1b .figure  <dig>
schematic diagram of breast cancer pathway.
brca <dig> plays a central role in breast cancer by connecting dna damage and chromatin remodeling to downstream processes such as cell cycle progression and dna repair.
black lines  represent biochemical pathways, red and green edges are novel and known ppis, respectively.
ovals and clouds represent proteins and protein complexes, respectively.
red ovals represent novel proteins that are associated with breast cancer pathway on the basis of the predicted interactions they form.
cdk <dig> is a cyclin-dependent kinase that functions in cell cycle progression and mitosis, and plays an essential role in g1/s transition through its activation of the e2f transcription factor family and g0/g <dig> transition by rb phosphorylation  <cit> .
e2f and rb play a regulatory role in the transcription of brca <dig>  <cit> , connecting cdk <dig> to brca <dig>  in further agreement with the observed interactions, cdk <dig> has high expression levels in cancer cells and participates in cell proliferation and transformation by enhancement of atf <dig> activity, a gene that physically interacts with brca <dig> .
furthermore, both brca <dig> and cdk <dig> are involved in cell cycle transition, further supporting a potential role for cdk <dig> in breast cancer.
aurkb has several functions during mitosis, including spindle assembly, chromosome segregation, and cytokinesis  <cit> .
aurkb has high sequence similarity with aurka, another protein of the aurora kinase family, however they are reported to differ functionally from each other during mitosis  <cit> .
it is shown that brca <dig> may be phosphorylated by aurka, resulting in impaired function of brca <dig> in g2/m transition  <cit> .
aurkb has a single reported interaction within breast cancer pathway through brcc complex  <cit> .
the interactions identified here add credibility to the involvement of this protein in breast cancer pathway.
smc1b is a meiosis-specific protein involved in chromosome segregation during anaphase, synapsis, and recombination  <cit> .
smc1b is also part of the cohesin complex, which includes smc <dig>  smc <dig>  rad <dig> and several other proteins  <cit> .
the cohesin complex plays a role in several cellular processes such as dna repair, gene expression regulation and chromosome segregation .
recent studies showed that several subunits of the cohesin complex are also important in dna damage response  <cit> .
in addition, smc1b has been linked to neck and head cancer  <cit> , further supporting a role for this protein in cancer.
we also examined the ppi network for mutations associated with resistance to breast cancer therapeutics doxorubicin and trastuzumab.
individual mutant proteins were analyzed against the human proteome  for their ppis at a recall of 23% at a precision of  <dig> %.
in this way,  <dig> personalized human ppi networks were predicted, each differing by a mutation in one gene only.
the  <dig> ppi profiles were compared to that of their corresponding control networks.
the list of these mutants is found in the table in additional file  <dig>  four mutations, p04637a, p04637b, p04637c and p04637d, in p <dig>  protein have been linked to resistance to the chemotherapeutic breast cancer drug, doxorubicin  <cit> .
the ppi profile for p04637b and p04637d was identical to that of the wild type.
however, the other two mutants showed some differences.
for example, p04626a and p04626c lost their interactions with the nuclear transcription factor y, nfyc  and the ubiquitin conjugating enzyme e <dig> l <dig>  involved in nuclear hormone receptors transcriptional activity, among others.
similarly, a truncated form of her <dig>  is responsible for resistance against her2-targeted breast cancer therapeutics such as trastuzumab  <cit> .
we observed that truncated-her <dig> lost several ppis including an interaction with a g-protein signaling rgs <dig>  which functions as an inhibitor of signal transduction, and an interaction with an early growth response protein erg <dig>  involved in cell differentiation.
of interest, the truncated her <dig> formed a new interaction with the tumor suppressor p <dig> protein.
a possible explanation for this novel interaction for the truncated her <dig> could be that segments of the deleted region might have physically hindered the availability of the region responsible for an interaction with p <dig> in the wild type form.
identification of novel molecular markers for seasonal allergic rhinitis
glucocorticoids  have a key role in the treatment of patients with seasonal allergic rhinitis  and other allergic disorders  <cit> .
because of this and difficulties in evaluating treatment response based on clinical signs and symptoms, there is a need for protein markers to monitor that response.
the identification of such markers is complicated by the involvement of a large number of inflammatory proteins in sar  <cit> .
we hypothesized that novel biomarkers could be identified among proteins predicted to interact with proteins belonging to known inflammatory pathways in sar including the acute phase response pathway, complement signaling pathway and glucocorticoids receptor pathway  <cit> .
proteins from the acute phase response pathway, complement signaling pathway and glucocorticoids receptor pathway were extracted from the ingenuity pathway analysis  software.
interactors of these proteins were selected from our predicted human ppi network.
we included secreted, membrane and cytoplasmic proteins, but excluded nuclear proteins.
we prioritized candidate biomarkers based on their number of known and predicted interactions with proteins known to be involved in sar-associated responses.
next, we focused on proteins with a high number of predicted interactions.
from the literature we extracted  <dig> proteins that belong to the acute phase response pathway, complement pathway, and glucocorticoids receptor pathway .
these proteins formed the known set of sar-associated proteins .
from our predicted human ppis, the proteins that interacted with sarp were determined.
a total of  <dig> proteins were found to interact with one or more sarp.
we prioritized five new proteins with a high number of total and predicted interactions to sarp as candidate biomarkers, namely prb <dig>  prb <dig>  sfn, lyn and akt <dig>  using elisa, we analyzed these candidates in nasal fluid from  <dig> patients with sar before and after gc treatment.
this study represented protein expression analysis for  <dig> samples .
it was observed that after gc treatment lyn concentration increased from  <dig>  ±  <dig>  pg/ml to  <dig>  ±  <dig>  pg/ml .
prb <dig> decreased from  <dig>  ±  <dig>  ug/ml to  <dig>  ±  <dig>  ug/ml  .
prb <dig> was not differentially expressed before and after treatment, and sfn and akt <dig> were not detectable in most samples.
differential protein expression for lyn and prb <dig> provides a good evidence for the possibility of using these proteins as novel molecular markers for sar.
altogether, the data presented here illustrates the suitability of the predicted ppis for identifying potential new molecular markers for human conditions.figure  <dig>
analysis of candidate proteins with elisa.
proteins were analyzed in nasal fluid from  <dig> patients with sar before and after gc treatment.
pre, patients before gc treatment; post, patients after gc treatment.
lyn and prb <dig> were differentially expressed before and after gc treatment with p-values of < <dig>  and < <dig> , respectively.
the proteome-wide ppi network can identify translation genes
the process of protein synthesis or translation is the process by which the genetic message embedded in mrnas is sequentially read and converted into polypeptide sequences.
due to its absolute requirement for the survival of a cell, this process has remained highly conserved through the course of evolution.
our predicted interactome included novel interactions for five human proteins q96dg <dig> , q08am <dig> , p <dig> , q9ukr <dig>  and p <dig>  with proteins known to play roles in the process of translation.
to study the involvement of these five proteins in translation, we subjected their corresponding yeast homologs  to experimental analysis.
first, we examined the effect of their deletion on stop-codon read-through using three different expression plasmids, pukc <dig>  pukc <dig> and pukc <dig> that carry premature stop codons uaa, uga and uag, respectively, within a β-galactosidase reporter gene.
as evident from an increase in relative β-galactosidase activity shown in figure 8a, the deletion of hap <dig>  erg <dig> and lys <dig> significantly altered the ability of ribosomes to detect all three stop codons.
to confirm that the observed elevation of β-galactosidase was at the translation level, mrna content of β-galactosidase was measured.
no difference between relative content of β-galactosidase mrnas was observed in deletion and control strains .figure  <dig>
novel involvement of hap <dig>  erg <dig> and lys <dig> in translation.
a) the relative β-galactosidase activity is determined by normalizing the activity of the mutant strains carrying different stop-codon read through cassettes to the control construct  in the wild type strain.
b) the relative mrna level is determined by normalizing the mrna content of the mutant strains carrying different premature stop-codon expression cassettes to those in the wild type.
c) increased sensitivity of hap2Δ, erg28Δ and lys12Δ to different translation inhibitory drugs.
sensitivity of the wild type strain was used as a point of reference.
sensitivity was quantified as low, moderate and high with respect to that for the wild type strain.
hap2Δ, lys12Δ, and erg28Δ show increased sensitivity to one or both streptomycin and/or cycloheximide.
d) effect of gene deletions on translation efficiency.
relative translation efficiency was measured using p <dig> plasmid containing gal-inducible promoter in lacz expression cassette normalized to mrna content.
values are related to translation efficiency of the control strain set at  <dig> .
we then further investigated the involvement of hap <dig>  erg <dig> and lys <dig> in translation by subjecting their deletion mutants to drugs that affect translation.
hap2∆, erg28∆ and lys12∆ showed altered levels of sensitivity to streptomycin and cycloheximide .
next, translation efficiency  was measured using an inducible lacz gene cassette on a p <dig> plasmid  <cit> .
deletion mutants for erg <dig> and lys <dig> had a drastic reduction in the rate of induced lacz synthesis further linking erg <dig> and lys <dig> to translation .
interestingly erg <dig> is a well-characterized protein involved in ergosterol biosynthetic pathway, the relation of which to translation is not readily expected.
however, in agreement with a link to translation, erg <dig> was previously shown to physically interact with a polysome associated mrna binding protein slf <dig>  <cit> , and a putative rna helicase spb <dig> that sediments with 66s pre-ribosomes  <cit> .
further, erg <dig> is localized to er membranes and a general link between sterol biosynthesis and translation has previously been proposed  <cit> .
identification of protein complexes within the human interaction network
protein complexes can be defined as a group of proteins that interact with each other to form a functional unit.
paracliques  <cit>  can be computationally identified as a sub group of proteins within the interaction network with high degree of interconnectivity and may define putative complexes.
given the size of the human ppi network, prediction of paracliques requires advanced computational approaches to complete a thorough analysis within a reasonable timeframe.
we have applied a novel graph theoretic approach to automatically identify paracliques within the network .
our analysis led to a number of interesting predictions.
for each paraclique, a statistical analysis of gene ontology  term enrichment was performed.
the table in additional file  <dig> lists the top go term for each paraclique along with a p-value for the observed enrichment.
for example, paraclique  <dig> is a complex of six proteins with  <dig> interactions .
o <dig>  is a cytoskeletal protein that acts as an adapter to bridge other proteins  to the cytoskeleton.
p <dig>  is a muscle protein involved in maintaining the structural integrity of sarcomeres and membranes associated with the myofibrils .
the rest of the members , p <dig> , p <dig>  and p <dig> ) are intermediated filament proteins.
on the basis of go enrichment , one may conclude that the activity of this complex is associated with cytoskeleton and structural integrity of the cell.
paraclique  <dig> is a complex of six proteins with  <dig> interactions .
q <dig>  is involved in cell adhesion and the remaining proteins , q <dig> , q <dig> , q8iwv <dig> , q9p <dig> , and q9uq <dig> ) are involved in cell surface interaction during nervous system development.
on the basis of go enrichment, we can assign this complex to cell adhesion .
paraclique  <dig> is a complex of five proteins with  <dig> interactions .
three of its members , p <dig>  and p <dig> ) are g protein-coupled receptor kinase and the remaining two  and q9nzu <dig> ) are calcium-binding proteins.
considering the fact that biological interaction between g-protein coupled receptor and calcium-binding proteins has been widely reported and seems essential in signaling pathways, one may conclude that this complex plays a role in g-protein coupled signaling pathway, a claim which is supported by enriched gene ontology term .
limitations and future work
while mp-pipe represents a significant step forward towards computing a complete human interactome, there remain a number of limitations which lead us to future work.
in order to operate at a reasonable precision rate, we have tuned our decision thresholds to be extremely conservative, resulting in a limited sensitivity of 23%.
future work will examine ways to continue to increase sensitivity/recall without sacrificing our false positive rate.
where mp-pipe has advantage over structure-based methods is in coverage: mp-pipe requires only sequence as input and is therefore applicable to all protein pairs.
however, in future work we will examine ways to capitalize on the rich information encoded in protein structure when such inputs are available.
at present, this represents only a small fraction of protein pairs, however, this proportion is expected to grow with ongoing large-scale protein structure determination initiatives.
as with all computational methods, another potential limitation in prediction accuracy is the quality of input data used to train mp-pipe.
as more experimental data of higher quality becomes available, we expect mp-pipe to also become more accurate.
lastly, we are continuing to apply parallelization and algorithmic optimizations to mp-pipe to further reduce runtimes for whole-proteome scans.
this will be critical if we are to investigate large numbers of organisms for comparative studies, or if we wish to compute personalized interactomes, accounting for the multitude of genetic variations that make each person’s interactome unique.
CONCLUSIONS
in this study, we present a comprehensive pair wise analysis and prediction of the entire human ppi network using the principles of short co-occurring polypeptide regions as mediators of ppis.
through this massive computational analysis, we predict approximately  <dig>  ppis, of which  <dig>  have not been reported previously.
the distribution of the novel ppis on the basis of sub-cellular localization, molecular function and biological process are very similar to those of previously reported interactions, highlighting the reliability of our predictions.
moreover, we demonstrate that mp-pipe predictions can effectively explain experimentally observed lgts-ms interaction data .
our predictions are useful for understanding cellular biology as a whole, with approximately  <dig>  protein complexes in our inferred interaction network.
furthermore, specific processes can be successfully interrogated using our new predictions: on the basis of inferred interactions we predict and experimentally confirm novel functions for proteins involved in translation, and identify new molecular markers for seasonal allergic rhinitis.
our analysis highlights the usefulness of the predicted ppis for functional analysis of the human proteome.
the speed associated with this approach sets the path for investigating the ppi map for individual humans in a timely fashion.
personal  ppi maps may improve our knowledge of network and personalized medicine.

 protein-protein interactions are essential molecular interactions that define the biology of a cell, its development and responses to various stimuli. physical interactions between proteins can form the basis for protein functions, communications, and regulation and controls within a cell. such interactions can result in the formation of protein complexes that perform specific tasks. similarly, internal and external signals are often realized and communicated through the formation of stable or transient ppis. due to their central importance to the integrity of communication networks within a cell, ppis are thought to involve important targets for drug discovery and are linked to a number of cellular conditions and diseases. our current knowledge of global ppi networks in different organisms is hindered by the constraints and limitations of existing experimental techniques amenable to high throughput ppi studies, such as yeast-two-hybrid and affinity purification combined with mass spectrometry. while both of these techniques have been successfully applied to global ppi detection in the yeast, saccharomyces cerevisiae, they suffer from significant shortcomings highlighted by the lack of overlap observed between the ppi data in different reports. the two benchmark large-scale yeast apms investigations have less than 25% overlap and this overlap is even less for the two classic y2h projects. only ppis are shared between all four studies, further highlighting the gap in our understanding of global ppi networks. although recent technical improvements are expected to increase the confidence of the detected ppis and hence fill some of the current gap of knowledge, increasing the coverage and quality of ppi networks remains an important challenge. computational tools offer time and cost effective alternatives to traditional wet-lab ppi detection tools. they may also be used as “filters” to increase confidence in data derived from wet-lab experiments. like other techniques, most computational tools also suffer from notable deficiencies. for example, most computational methods rely heavily on previously reported data. assuming that there are inherent discrepancies in the training data, the accuracies of such tools to detect new interactions are often questionable. moreover, novel interaction domains or motifs are likely to be missed by methods that rely heavily on the structures or other high-level features of protein pairs known to interact. another major shortcoming of computational tools is that they are often too computationally intensive, making them impossible to use for proteome-wide analysis. to date, no comprehensive all-against-all analysis of the entire human ppi network has been possible. a small number of large-scale computational ppi prediction methods have recently been published. although these methods have provided important contributions to the field, they are not applicable to the entire human proteome due to computational complexity, availability of input protein features, or unacceptably high false positive rates. for example, a recent study by elefsinioti et al. examined five million protein pairs and predicted “high confidence” interactions. given a conservative estimate of human proteins, leading to million possible pairs, elefsinioti et al. have examined only 2% of the potential interactome while others have examined just over 7% and % of the total interactome. presumably these methods were limited to examining only small subsets of protein pairs due to computational complexity or the availability of input protein features. for example, the method of elefsinioti et al. requires complex features for each protein relating to annotated function, sequence-derived attributes, and network structure. likewise, the method of zhang et al. requires structural information for both proteins in the putative interaction and is therefore only applicable to human proteins. when considering protein pairs rather than individual proteins, approximately 50% sequence coverage results in an examination of at most 25% of the possible ppis. in fact, zhang et al. report that they were able to develop models for million interactions, representing % of the million possible interactions. even if these methods could be applied to all human protein pairs, typical false positive rates will render existing methods unusable on larger data sets. for example, considering that the method of elefsinioti et al. predicts “high confidence” interactions among only % of protein pairs, then we can reasonably expect nearly million “high confidence” predicted interactions if their method were to be applied to the entire human proteome. this is an order of magnitude higher than the largest current estimate of the true size of the human interactome, leaving the experimenter to weed through a multitude of false positive predictions to find the few true interactions. likewise, using a previously published computational method, zhang et al. recently reported a false positive rate implying % precision, and their recall over an independent test set of newly reported ppis is less than 7%. consequently, there is a need for the development of efficient tools that are readily amenable to proteome-scale ppi prediction. this is especially important as the field of personalized medicine will benefit tremendously from a fast and accurate method that can predict the global ppi maps of different individuals from their genomic sequences alone. a subset of cellular ppis is mediated by defined short, linear polypeptide sequences. leveraging this fact, a number of computational tools have been developed to detect ppis solely on the basis of primary sequence. such approaches do not rely on known structures or other protein features that are not easily deduced from primary protein sequences, and are thus, in principle, able to interrogate portions of the proteome that are inaccessible to other methods. some of their predictions have been confirmed by tandem affinity purification, in vitro binding assays, and in vivo functional analysis. an added benefit of sequence-based ppi prediction is that short polypeptide sequences in one organism can be used to predict ppis in another. we note that, while the wide applicability of sequence-based ppi prediction methods is clearly a strength, in not using structural predictions, such techniques may be unable to account for structural features such as binding site accessibility or widespread contacts between non-contiguous residues. we have developed a computational tool termed the protein interaction prediction engine that uses co-occurrence of short polypeptide regions to detect novel ppis in s. cerevisiae. although pipe was able to analyze potential ppis within certain proteomes, applying this tool to more complex proteomes remained infeasible due to computational complexity. analyzing the ~ million protein pairs in the human proteome was estimated to require approximately million cpu-hours of computation. in order to study the human ppi network, we developed a new massively parallel version of pipe, which we call mp-pipe. mp-pipe overcomes some of the limitations of existing methods through computational acceleration of the algorithm and improved precision. we present a comprehensive all-against-all analysis of the human proteome and study its biological properties. we then demonstrate the accuracy and utility of the mp-pipe inferred interactome using a range of functional assays.  mp-pipe performance and scalability enables computational scan of entire human proteome one of the main issues when predicting human protein interactions on a large scale, which does not occur for simpler organisms such as s. cervisiae or c. elegans, is the complexity of the human proteome. more precisely, when predicting human protein interactions using previous methods, the compute time to process a single human protein pair can vary between several seconds and more than 12 hours. this effect has so far only been observed for the human protein interactions. our previous method was ranked highly in terms of prediction accuracy in an independent comparison study. however, it would be unable to process all human protein pairs in our lifetime. therefore, we developed an algorithm called mp-pipe, capable of performing global ppi analysis of the human proteome. although the task of performing a proteome-wide, all-to-all prediction within the human proteome is still extremely computationally expensive for mp-pipe, it still remained a feasible task and was completed within three months though massive parallelization. from a computer science perspective, the main challenge is the massive load imbalance of the parallelization. as shown in figure 1a, for the vast majority of protein pairs, protein interaction prediction can be performed in seconds. however, for some protein pairs, the process takes minutes or hours, more than 12 hours in extreme cases. solving this load imbalance in an efficient manner is the main computational contribution of mp-pipe.figure mp-pipe benchmark performance. a) distribution of running times for human protein-protein interaction prediction. numbers above bars indicate approximate number of protein pairs with a running time within the given range. b) performance for different numbers of threads per worker on the large cluster. average running times for random protein pairs or random protein pairs, using one worker process. c) performance for different numbers of workers on the large cluster. average running times for random protein pairs, using threads per worker. in the following, we discuss the runtime performance of mp-pipe on different hardware architectures which eventually enabled us to perform global ppi analysis of a human cell within three months. more precisely, we tested our mp-pipe solution on three different compute clusters. these clusters included a six node cluster with total compute cores, a node cluster with total compute cores, and a node cluster with total hardware supported threads. the performance of mp-pipe was initially tested on a single large cluster node with varying numbers of threads, and then in a second test we increased the number of nodes. the test data set consisted of random protein pairs. however, this data set proved to be too large to compute using a small number of threads, so a subset containing random pairs was used to examine the runtime performance of the code with 1– threads and then the full pair data set was used for tests with or more threads. for those test cases that were performed over the smaller pair subset, runtimes were extrapolated to estimate the runtime over the full pair dataset. the results are shown in figure  the speedup curve shown in figure 1b shows a dramatic performance improvement using up to threads and then a slight improvement from there up to threads. we found that using more than threads creates memory problems. for the second test, we increased the number of large cluster nodes used, where each node ran one mp-pipe worker with worker threads. the results are shown in figure 1c. the performance of mp-pipe scales almost linearly as the number of compute nodes increases. this scalability property of mp-pipe enabled us to perform global ppi analysis of the human proteome within three months. verification of mp-pipe against experimental data as with other ppi prediction methods, mp-pipe relies on previously reported interaction data to make its predictions. the quality of the predictions made is inherently determined on the quality of this input data. to determine the prediction accuracy of mp-pipe for human ppis we conducted a leave-one-out test of mp-pipe using the experimentally verified, high-confidence human ppis taken from biogrid and randomly chosen negative protein pairs. choosing negative data in this way avoids sources of bias introduced by other methods. the loo tests were conducted as follows: mp-pipe was run times, one for each experimentally verified interacting protein pair. for each test run, we removed the known interaction from the database. in this manner, we create a state where mp-pipe is not aware of the experimentally verified ppi, as if that interaction had not been measured yet. we then asked mp-pipe to predict whether or not proteins a and b interact. the same was then done for the negative set of randomly selected protein pairs that were expected to not interact. once finished, the total mp-pipe predictions made were sorted by their pipe score. examining this sorted list allows us to set our decision threshold operating point. given any “accept threshold”, we can then see how many false positives and negatives were produced during our test runs. given the expected ratio of non-interacting protein pairs for each interacting protein pair, typically a threshold that achieves an extremely high specificity is chosen in order to minimize out false positive rate. at the chosen operating point, mp-pipe produced true positives, true negatives, false positives and false negatives from the total test predictions made. these results are summarized in the confusion matrix in table  table confusion matrix for the leave-one-out cross-validation tests used to determine the prediction accuracy of mp-pipe known interacting pairs assumed non-interacting pairs total predicted to interact predicted not to interact total since the ratio of known interacting pairs to assumed non-interacting pairs in our test set is not representative of the true ratio expected among all protein pairs within the h. sapiens proteome, the results in the above confusion matrix require adjustment. this adjustment to account for the true prevalence of ppis among all protein pairs leads to a more conservative and realistic estimate of predictive performance of mp-pipe. we have used a ratio of non-interacting protein pairs per interacting pair. we feel this is a more realistic estimate given the expected sparsity of the actual interaction network and the range of estimates reported in previous studies. the ratio-adjusted confusion matrix adjusted for this ratio is shown in table  table the ratio-adjusted confusion matrix the leave-one-out cross-validation tests used to determine the prediction accuracy of mp-pipe known interacting pairs assumed non-interacting pairs total predicted to interact predicted not to interact total a wide variety of performance metrics are commonly used to assess ppi prediction methods. these are summarized and computed in table  below.table statistical performance metrics for mp-pipe based on true negatives, true positives, false negatives, and false positives seen in the leave-one-out cross-validation tests, corrected to use a positive: negative ratio of 1:100 statistical measure definition value tnfp+tn tptp+fn tptp+fp tp+tntp+fp+fn+tn 2tp2tp+fp+fn tpxtn−fpxfntp+fptp+fntn+fptn+fn this leave-one-out test was repeated with all homologs removed from our human dataset as in. this reduced our protein sequence set from to and our experimentally verified human ppi set from to pairs. removing homologs at the 40% identity level effectively removes all protein isoforms from our loo performance assessment. this leads to a conservative estimate of performance as not removing the homologs could potentially inflate the reported statistical performance figures. as can be seen in the figure in additional file, the recall of our method is slightly reduced when homologous proteins are removed from our dataset, however if we adjust our decision threshold to maintain a recall of 23%, we still achieve a precision of %. all-against-all scan of the human proteome after three months of 24/ computation on the fully dedicated nodes of the large cluster, mp-pipe completed the scan of the human proteome. with the chosen operating point as described in the previous section, mp-pipe predicted protein interactions. of these high confidence predictions, protein interactions have never been reported previously. given that human protein interactions are known and were included in the mp-pipe database and would therefore be predicted to interact, mp-pipe has potentially more than quadrupled our knowledge of the human interaction network. at the chosen operating point, mp-pipe data covers more than one fifth of the estimated human ppi landscape. in comparison, elefsinioti et al. have examined 2% of the interactome while others have examined just over 7% and % of the total interactome. the list of the reported interactions is found in the table in additional file the list is ordered according to pipe score, where higher values represent higher confidence levels for an interaction. distribution of run time for different human protein pairs is illustrated in figure 1a. the length of the query proteins does not appear to correlate with runtime. the analysis performed on mp-pipe’s predicted interactions throughout the rest of this study will cover both the known and novel interactions, unless stated otherwise. besides leave one out cross-validation, another standard method for evaluating ppis is to check whether the proteins pairs predicted to interact are co-located within the same cellular component, have the same molecular function, are involved in the same biological process or have a common third party interacting partner. the results of this analysis are shown in table  and figure  the overall profiles for the predicted interacting pairs that have not been detected before, on the basis of cellular localization, process and function resembles that of previously reported pairs. certain differences however are noticeable. for example, a new association for “metal ion binding” and “transcription” is observed for the predicted interactions and not for those that have been previously reported. similarly, there is a strong association between “immune response” and “signal transduction” for the predicted interactions. as indicated in table  the percentage of predicted interacting protein pairs that have similar function, occur in the same cellular component and participate in the same cellular process is %, which is consistent with the percentage for previously reported protein pairs. in contrast, only % of randomly selected protein pairs share these three traits. it is important to note that the pipe algorithm has no previous knowledge of the protein location, molecular function of proteins, or the biological processes in which they are involved. such an association for protein pairs predicted by mp-pipe further highlights the ability of this method to predict interactions that can be supported by independent parameters. such contextual information can also be used to assign an independent degree of confidence for ppi predictions. for example, higher confidence might be assumed for a protein pair where both proteins occur in the same location and share the same go term for a cellular process. this information is presented in the table in additional file and can be used to form a priority list of interactions for further biological analysis.table percentages of homo sapiens pairs in which both partners share the same go slim annotation as well as third party interactions derived from go annotation third party interaction cellular component molecular function biological process cc & mf & bp *p-value <1e- distribution of the interacting protein pairs on the basis of subcellular localization, molecular function and cellular process for both previously detected interactions and interactions unique to this study normalized by the number of possible pairs with both go terms. the overall co-occurrence for pairs that were previously not reported is similar to that of previously reported interactions. the observed enrichment for certain categories within predicted interactions may represent new association or cross-communication. for example, in panel b, a co-occurrence for “metal ion binding” and “transcription” is observed for predictions that were not previously reported. similarly, in panel c, “immune response” and “signal transduction” have a more profound association among the predicted interacting pairs in this study. in addition to the above cross-validation, we independently evaluated the competence of our predictions by evaluating experimental data gathered using the lentivirus-delivered, gateway-compatible affinity tagging system coupled with mass spectrometry approach that has been recently developed for the identification of ppis in mammalian cell lines. the lgts system uses a versatile affinity -tag constructed in-frame with a gateway cassette consisting of 3x flag, 6x his, and 2x streptactin epitopes, with flag and his separated by dual tev protease cleavage sites for efficient affinity purification. using this approach, we stably expressed four, rnf, h2afx, and rbbp ) c-terminal affinity tagged chromatin-related proteins in human embryonic kidney cells that play an important role in the epigenetic control of chromatin structure and gene expression, transcriptional repression, nucleosome remodeling, and chromatin assembly. these tagged proteins were affinity-purified in one step on anti-flag resins and the interacting proteins were identified by tandem mass spectrometry.figure affinity purification experiments using p, q, p, and q as baits. immunoblot confirming the expression of the indicated flag-tagged chromatin proteins using antibody against the 3x flag epitope. two independent flag tag constructs of each chromatin related protein was constructed for affinity purifications to eliminate background contaminants and to uncover highly reproducible interactions. molecular masses of marker proteins by sds-page are indicated. representative functional clusters identified from affinity purification data and expanded by mp-pipe predictions. tagged-baits are shown by yellow nodes. blue nodes represent co-purifying proteins identified through affinity purification. purple nodes represent proteins added to the functional clusters through mp-pipe predictions. red dashed edges represent previously reported binary interactions identified in literature experimental data and green solid edges represent novel mp-pipe binary interaction predictions. as expected, we recovered both the bait and several well-known interacting protein partners, such as the interaction between the tagged histone binding protein, rbbp and subunits of the core histone deacetylase complex and rbbp ), confirming the overall efficacy of the protein purification procedure employed in the identification of co-purifying interacting proteins. consistent with the biological expectation, these co-purifying proteins were enriched for more chromatin related functions such as chromatin organization, binding and assembly; nucleosome assembly; histone ubiquitination; and transcriptional regulation. examples of functional clusters identified through the lgts-ms based method are shown in figure 3b. to investigate mp-pipe’s ability to explain the observed lgts-ms data, we computed the precision and recall of mp-pipe predicted interactions. this is summarized in table  where reachable proteins are defined as those proteins that interact directly or through one or two intermediary proteins. this accounts for the fact that a bait and prey observed to co-purify in a lgts-ms experiment may, in fact, interact indirectly through one or more intermediary proteins. for the four baits, previously known ppi interactions can only explain on average % of the co-purifying proteins. using mp-pipe predictions increases our recall by ~3-fold while maintaining comparable precisions.table overlap of co-purifying proteins identified through lgts-ms with previously reported interactions and mp-pipe predictions reachable proteins prey reached recall 1 precision 2 bait # of prey known mp-pipe known mp-pipe known mp-pipe known mp-pipe total 1276 258 676 139 374 % % % % 1recall calculated as reached/# of prey. 2precision calculated as reached/reachable. our predicted interactions appear to have a wide coverage of the human proteome. for instance, of the human potential open reading frames included in this study, were found in our prediction list for a coverage of approximately 50%. since a total of interactions were predicted, on average there appears to be approximately interactions for each protein found in the prediction list. as illustrated in figure  approximately 32% of the predicted interactions occur in the nucleus, followed by 21% in the cytoplasm. in fact, the distribution of the identified interactions is very consistent with those of the previously reported ones. this distribution is also in accordance with the previously reported ppi distribution in s. cerevisiae. of interest are membrane proteins, which although not readily amenable to experimental assays, received good coverage using mp-pipe. the full range of biological processes and molecular functions is also well covered. on the basis of expression level, % and % of highly and low expressed proteins, respectively, also appear in the list of ppis. we also examined the interactions for fibroblast growth factors and cyclin-dependent kinases with fibroblast growth factor receptors and regulatory inhibitors and activators of cyclin-dependent kinases, respectively. these represent examples of proteins that share high similarity in primary sequence and molecular function, yet have differences in substrate specificity and regulatory factors. shown in the table in additional file there are clear differences in interacting partners for different members of fgf and cdk proteins. altogether these observations suggest that our prediction method appears to be inclusive and specific, and is amenable to diverse set of proteins presenting a good coverage of the proteome.figure number and percentage of co-localized interacting pairs by go components in previously reported data compared with those reported in this study only. note that since proteins can have multiple tags, interacting pairs can be co-localized in several components and can be counted more than once. network-wide analysis of hubs and betweenness centrality in a ppi network, the degree of interaction for a target protein is believed to be a good indicator for the biological importance of that protein within the system. removal of the highly connected proteins or “hubs” appears to have a more profound effect on the integrity of the network by reducing the size of the largest connected module, than removal of random proteins. we studied the top and hubs with the highest number of interactions within our predicted ppi network, and observed very high enrichment for proteins that affect transcription and gene expression. transcription factors mediate differential genetic programming and hence are of central importance in developmental biology, responses to stimuli, disease progression, etc. betweenness centrality is another topological feature of a network and evaluates the number of shortest paths that pass through a given node. therefore, high betweenness centrality for a protein represents the relative number of shortest paths that are associated with that protein. consequently, proteins with high betweenness centrality are thought to play a central role in the cross-talk and communication between interconnected modules of a network by forming “traffic bottlenecks” for communication. we evaluated the top and proteins with highest betweenness centrality values within our predicted network. consistent with the expected role of these proteins in signaling, we observed that they were highly enriched for proteins involved in intracellular communication, or for which communication is of central importance.table enrichment of biological process for proteins with highest hub degree or betweeness centrality measurements biological process top 10 top 25 top 50 # prot p-value # prot p-value # prot p-value hubs transcription regulation regulation of gene expression b.c. protein kinase activity regulation of cell death signaling centrality measurements are often used to predict the possible involvement of a protein in disease etiology and progression. some studies suggest that hubs are likely enriched for disease proteins, whereas others incline towards betweenness centrality as a better indicator. we therefore examined a possible relationship between the top proteins with the highest degrees of centrality and their reported involvement in disease progression. as illustrated in figure  both hub and betweenness centralities appear to be good indicators for disease proteins. however, betweenness centrality appeared to have a better correlation than hubs for disease proteins. a ranked list of top proteins according to their centrality measures is reported in additional file and the table in additional file. we note that the relationship between connectivity and disease is dependent on a variety of factors, particularly gene essentiality, which we have not investigated here in depth.figure comparing the number of disease-associated proteins with high degree and high betweenness centrality. proteins with highest betweenness centrality appear to be more enriched for disease proteins than hubs. the usefulness of the predicted interactions in biological investigations our computationally predicted interactome represents a comprehensive all-to-all interaction network in humans. this network generates a wide range of testable hypotheses concerning biological processes, and informs our understanding of the overall architecture of cellular function. here, we demonstrate the usefulness of this new predicted interactome through prediction of gene functions, experimental verifications and analysis of putative protein complexes. using the predicted human protein interaction network to assign breast cancer proteins breast cancer is the most commonly diagnosed form of cancer among women. brca and to some extent brca are the two key genes associated with breast cancer progression. breast cancer susceptibility has been related to a mutation of brca. carriers of brca mutations have a 50-80% increased risk of developing breast cancer. it is estimated that 10% of western women fall in this category. while the tumor suppression property of brca is well investigated, the molecular mechanism of its activity in tumor prevention is not fully understood. figure  illustrates a brief overview of the breast cancer pathway where brca plays a central role. as illustrated, brca is directly associated with several cellular processes including chromatin remodeling, dna damage checkpoint activation, dna damage sensing, and dna double stranded break repair. brca plays an essential role in delaying cell cycle progression by its dna damage checkpoint activity. atm phosphorylation of p a tumor suppressor protein, is mediated by brca and, in the presence of dna damage, delays or arrests g1/s transition. brca is important during s phase and g2/m checkpoint activation through its regulation of kinase activity of chk. upon dna damage, h2ax is phosphorylated by atm and atr and recruits mdc and rnf to the site of the damage. subsequently, brca is translocated to the site of damage by ubiquitination of h2a through rnf and ubc and interacts with the mre11/rad50/nbs complex that is involved in double stranded dna break repair. examining the proteins involved in the breast cancer pathway for ppis, mp-pipe predicted over interactions, of which directly involve brca. studying these interactions can expand our current understanding of the breast cancer pathway. a number of interesting factors were found to form novel interactions with multiple proteins associated with the breast cancer pathway, including cdk aurkb, and smc1b.figure schematic diagram of breast cancer pathway. brca plays a central role in breast cancer by connecting dna damage and chromatin remodeling to downstream processes such as cell cycle progression and dna repair. black lines represent biochemical pathways, red and green edges are novel and known ppis, respectively. ovals and clouds represent proteins and protein complexes, respectively. red ovals represent novel proteins that are associated with breast cancer pathway on the basis of the predicted interactions they form. cdk is a cyclin-dependent kinase that functions in cell cycle progression and mitosis, and plays an essential role in g1/s transition through its activation of the e2f transcription factor family and g0/g transition by rb phosphorylation. e2f and rb play a regulatory role in the transcription of brca, connecting cdk to brca in further agreement with the observed interactions, cdk has high expression levels in cancer cells and participates in cell proliferation and transformation by enhancement of atf activity, a gene that physically interacts with brca. furthermore, both brca and cdk are involved in cell cycle transition, further supporting a potential role for cdk in breast cancer. aurkb has several functions during mitosis, including spindle assembly, chromosome segregation, and cytokinesis. aurkb has high sequence similarity with aurka, another protein of the aurora kinase family, however they are reported to differ functionally from each other during mitosis. it is shown that brca may be phosphorylated by aurka, resulting in impaired function of brca in g2/m transition. aurkb has a single reported interaction within breast cancer pathway through brcc complex. the interactions identified here add credibility to the involvement of this protein in breast cancer pathway. smc1b is a meiosis-specific protein involved in chromosome segregation during anaphase, synapsis, and recombination. smc1b is also part of the cohesin complex, which includes smc smc rad and several other proteins. the cohesin complex plays a role in several cellular processes such as dna repair, gene expression regulation and chromosome segregation. recent studies showed that several subunits of the cohesin complex are also important in dna damage response. in addition, smc1b has been linked to neck and head cancer, further supporting a role for this protein in cancer. we also examined the ppi network for mutations associated with resistance to breast cancer therapeutics doxorubicin and trastuzumab. individual mutant proteins were analyzed against the human proteome for their ppis at a recall of 23% at a precision of %. in this way, personalized human ppi networks were predicted, each differing by a mutation in one gene only. the ppi profiles were compared to that of their corresponding control networks. the list of these mutants is found in the table in additional file four mutations, p04637a, p04637b, p04637c and p04637d, in p protein have been linked to resistance to the chemotherapeutic breast cancer drug, doxorubicin. the ppi profile for p04637b and p04637d was identical to that of the wild type. however, the other two mutants showed some differences. for example, p04626a and p04626c lost their interactions with the nuclear transcription factor y, nfyc and the ubiquitin conjugating enzyme e l involved in nuclear hormone receptors transcriptional activity, among others. similarly, a truncated form of her is responsible for resistance against her2-targeted breast cancer therapeutics such as trastuzumab. we observed that truncated-her lost several ppis including an interaction with a g-protein signaling rgs which functions as an inhibitor of signal transduction, and an interaction with an early growth response protein erg involved in cell differentiation. of interest, the truncated her formed a new interaction with the tumor suppressor p protein. a possible explanation for this novel interaction for the truncated her could be that segments of the deleted region might have physically hindered the availability of the region responsible for an interaction with p in the wild type form. identification of novel molecular markers for seasonal allergic rhinitis glucocorticoids have a key role in the treatment of patients with seasonal allergic rhinitis and other allergic disorders. because of this and difficulties in evaluating treatment response based on clinical signs and symptoms, there is a need for protein markers to monitor that response. the identification of such markers is complicated by the involvement of a large number of inflammatory proteins in sar. we hypothesized that novel biomarkers could be identified among proteins predicted to interact with proteins belonging to known inflammatory pathways in sar including the acute phase response pathway, complement signaling pathway and glucocorticoids receptor pathway. proteins from the acute phase response pathway, complement signaling pathway and glucocorticoids receptor pathway were extracted from the ingenuity pathway analysis software. interactors of these proteins were selected from our predicted human ppi network. we included secreted, membrane and cytoplasmic proteins, but excluded nuclear proteins. we prioritized candidate biomarkers based on their number of known and predicted interactions with proteins known to be involved in sar-associated responses. next, we focused on proteins with a high number of predicted interactions. from the literature we extracted proteins that belong to the acute phase response pathway, complement pathway, and glucocorticoids receptor pathway. these proteins formed the known set of sar-associated proteins. from our predicted human ppis, the proteins that interacted with sarp were determined. a total of proteins were found to interact with one or more sarp. we prioritized five new proteins with a high number of total and predicted interactions to sarp as candidate biomarkers, namely prb prb sfn, lyn and akt using elisa, we analyzed these candidates in nasal fluid from patients with sar before and after gc treatment. this study represented protein expression analysis for samples. it was observed that after gc treatment lyn concentration increased from  ±   pg/ml to  ±   pg/ml. prb decreased from  ±  ug/ml to  ±  ug/ml. prb was not differentially expressed before and after treatment, and sfn and akt were not detectable in most samples. differential protein expression for lyn and prb provides a good evidence for the possibility of using these proteins as novel molecular markers for sar. altogether, the data presented here illustrates the suitability of the predicted ppis for identifying potential new molecular markers for human conditions.figure analysis of candidate proteins with elisa. proteins were analyzed in nasal fluid from patients with sar before and after gc treatment. pre, patients before gc treatment; post, patients after gc treatment. lyn and prb were differentially expressed before and after gc treatment with p-values of < and <, respectively. the proteome-wide ppi network can identify translation genes the process of protein synthesis or translation is the process by which the genetic message embedded in mrnas is sequentially read and converted into polypeptide sequences. due to its absolute requirement for the survival of a cell, this process has remained highly conserved through the course of evolution. our predicted interactome included novel interactions for five human proteins q96dg, q08am, p, q9ukr and p with proteins known to play roles in the process of translation. to study the involvement of these five proteins in translation, we subjected their corresponding yeast homologs to experimental analysis. first, we examined the effect of their deletion on stop-codon read-through using three different expression plasmids, pukc pukc and pukc that carry premature stop codons uaa, uga and uag, respectively, within a β-galactosidase reporter gene. as evident from an increase in relative β-galactosidase activity shown in figure 8a, the deletion of hap erg and lys significantly altered the ability of ribosomes to detect all three stop codons. to confirm that the observed elevation of β-galactosidase was at the translation level, mrna content of β-galactosidase was measured. no difference between relative content of β-galactosidase mrnas was observed in deletion and control strains.figure novel involvement of hap erg and lys in translation. a) the relative β-galactosidase activity is determined by normalizing the activity of the mutant strains carrying different stop-codon read through cassettes to the control construct in the wild type strain. b) the relative mrna level is determined by normalizing the mrna content of the mutant strains carrying different premature stop-codon expression cassettes to those in the wild type. c) increased sensitivity of hap2Δ, erg28Δ and lys12Δ to different translation inhibitory drugs. sensitivity of the wild type strain was used as a point of reference. sensitivity was quantified as low, moderate and high with respect to that for the wild type strain. hap2Δ, lys12Δ, and erg28Δ show increased sensitivity to one or both streptomycin and/or cycloheximide. d) effect of gene deletions on translation efficiency. relative translation efficiency was measured using p plasmid containing gal-inducible promoter in lacz expression cassette normalized to mrna content. values are related to translation efficiency of the control strain set at. we then further investigated the involvement of hap erg and lys in translation by subjecting their deletion mutants to drugs that affect translation. hap2∆, erg28∆ and lys12∆ showed altered levels of sensitivity to streptomycin and cycloheximide. next, translation efficiency was measured using an inducible lacz gene cassette on a p plasmid. deletion mutants for erg and lys had a drastic reduction in the rate of induced lacz synthesis further linking erg and lys to translation. interestingly erg is a well-characterized protein involved in ergosterol biosynthetic pathway, the relation of which to translation is not readily expected. however, in agreement with a link to translation, erg was previously shown to physically interact with a polysome associated mrna binding protein slf, and a putative rna helicase spb that sediments with 66s pre-ribosomes. further, erg is localized to er membranes and a general link between sterol biosynthesis and translation has previously been proposed. identification of protein complexes within the human interaction network protein complexes can be defined as a group of proteins that interact with each other to form a functional unit. paracliques can be computationally identified as a sub group of proteins within the interaction network with high degree of interconnectivity and may define putative complexes. given the size of the human ppi network, prediction of paracliques requires advanced computational approaches to complete a thorough analysis within a reasonable timeframe. we have applied a novel graph theoretic approach to automatically identify paracliques within the network. our analysis led to a number of interesting predictions. for each paraclique, a statistical analysis of gene ontology term enrichment was performed. the table in additional file lists the top go term for each paraclique along with a p-value for the observed enrichment. for example, paraclique is a complex of six proteins with interactions. o is a cytoskeletal protein that acts as an adapter to bridge other proteins to the cytoskeleton. p is a muscle protein involved in maintaining the structural integrity of sarcomeres and membranes associated with the myofibrils. the rest of the members, p, p and p ) are intermediated filament proteins. on the basis of go enrichment, one may conclude that the activity of this complex is associated with cytoskeleton and structural integrity of the cell. paraclique is a complex of six proteins with interactions. q is involved in cell adhesion and the remaining proteins, q, q, q8iwv, q9p, and q9uq ) are involved in cell surface interaction during nervous system development. on the basis of go enrichment, we can assign this complex to cell adhesion. paraclique is a complex of five proteins with interactions. three of its members, p and p ) are g protein-coupled receptor kinase and the remaining two and q9nzu ) are calcium-binding proteins. considering the fact that biological interaction between g-protein coupled receptor and calcium-binding proteins has been widely reported and seems essential in signaling pathways, one may conclude that this complex plays a role in g-protein coupled signaling pathway, a claim which is supported by enriched gene ontology term. limitations and future work while mp-pipe represents a significant step forward towards computing a complete human interactome, there remain a number of limitations which lead us to future work. in order to operate at a reasonable precision rate, we have tuned our decision thresholds to be extremely conservative, resulting in a limited sensitivity of 23%. future work will examine ways to continue to increase sensitivity/recall without sacrificing our false positive rate. where mp-pipe has advantage over structure-based methods is in coverage: mp-pipe requires only sequence as input and is therefore applicable to all protein pairs. however, in future work we will examine ways to capitalize on the rich information encoded in protein structure when such inputs are available. at present, this represents only a small fraction of protein pairs, however, this proportion is expected to grow with ongoing large-scale protein structure determination initiatives. as with all computational methods, another potential limitation in prediction accuracy is the quality of input data used to train mp-pipe. as more experimental data of higher quality becomes available, we expect mp-pipe to also become more accurate. lastly, we are continuing to apply parallelization and algorithmic optimizations to mp-pipe to further reduce runtimes for whole-proteome scans. this will be critical if we are to investigate large numbers of organisms for comparative studies, or if we wish to compute personalized interactomes, accounting for the multitude of genetic variations that make each person’s interactome unique.  in this study, we present a comprehensive pair wise analysis and prediction of the entire human ppi network using the principles of short co-occurring polypeptide regions as mediators of ppis. through this massive computational analysis, we predict approximately ppis, of which have not been reported previously. the distribution of the novel ppis on the basis of sub-cellular localization, molecular function and biological process are very similar to those of previously reported interactions, highlighting the reliability of our predictions. moreover, we demonstrate that mp-pipe predictions can effectively explain experimentally observed lgts-ms interaction data. our predictions are useful for understanding cellular biology as a whole, with approximately protein complexes in our inferred interaction network. furthermore, specific processes can be successfully interrogated using our new predictions: on the basis of inferred interactions we predict and experimentally confirm novel functions for proteins involved in translation, and identify new molecular markers for seasonal allergic rhinitis. our analysis highlights the usefulness of the predicted ppis for functional analysis of the human proteome. the speed associated with this approach sets the path for investigating the ppi map for individual humans in a timely fashion. personal ppi maps may improve our knowledge of network and personalized medicine. 
on the basis of short co-occurring polypeptide regions, we developed a tool called mp-pipe capable of predicting a global human ppi network within 3 months.
 our knowledge of global protein-protein interaction networks in complex organisms such as humans is hindered by technical limitations of current methods.  on the basis of short co-occurring polypeptide regions, we developed a tool called mp-pipe capable of predicting a global human ppi network within 3 months. with a recall of 23% at a precision of %, we predicted putative ppis. we demonstrate the usefulness of these predictions through a range of experiments.  the speed and accuracy associated with mp-pipe can make this a potential tool to study individual human ppi networks for personalized medicine. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords protein-protein interactionscomputational predictionhuman proteomemassively parallel computingpersonalized medicineinteractomenetwork analysisissue-copyright-statement© the author 2014 