A Network-based Approach for Predicting Missing Pathway Interactions
[['Networks of protein interactions can reveal how complex molecular processes are activated in the cell .', 'However , even for model species , only a fraction of true physical interactions are known [1] , [2] and experimental verification of all remaining potential interactions is unlikely in the near future .', 'Furthermore , interactions are often condition- or tissue-specific [3] while current experimental methods often focus on one condition and one cell type [4] .', 'Thus , computational techniques to predict protein interactions have flourished as a means to build more complete interaction maps [5] , [6] .', 'Signaling pathways are subnetworks of proteins that communicate via a series of interactions and are often only activated under specific conditions ( e . g . stress response , development , etc . ) .', 'Perturbations of proteins within such pathways have been linked to several diseases [7] .', 'In addition , pathways are often conserved , thus studying their interactions in model organisms may help elucidate cellular response mechanisms in other organisms [8] .', "Signaling pathways typically contain upstream proteins ( e . g . receptors on the cell's surface ) that sense changes in the environment or that are directly involved in host-pathogen interactions .", 'These proteins trigger a signaling cascade that leads to downstream transcription factors ( TFs ) , which consequently carry forth regulatory programs .', 'The former set of proteins can be considered sources that transmit information to a set of targets .', 'Experimental protocols can infer source proteins based on their interactions with external stimuli ( e . g . host-pathogen interactions [9] ) , and likewise targets can be determined via expression or knockdown assays .', 'This motivated several techniques that have been proposed to extract pathways from global interaction networks by searching for efficient and robust paths between the given sets of sources and targets [10]–[13] .', 'These techniques , however , do not try to infer putative interactions that are missing from the network .', "We model this problem computationally by searching for missing edges that increase the network's ability to explain the signaling cascade from sources to targets .", 'Many methods have been proposed to computationally predict protein-protein interactions .', 'These methods leverage a variety of data sources , including physical docking models and protein structure [14] , [15] , evidence based on orthologous proteins in related species [16] , microarray expression profiles [17]–[21] , literature mining [22] , sequence-level features [23]–[27] , or a combination of heterogeneous features to learn a predictive model or classifier [28]–[32] ( for reviews , see [5] , [6] ) .', 'Network-only approaches range from completing defective cliques [33] to analyses based on the shared topology or the distance between two candidate proteins [34] , [35] to embeddings of the network to find non-interacting but adjacent proteins in the new space [36] , [37] .', 'None of these approaches , however , leverage known sources and targets to make pathway-aware predictions .', 'Further , most other approaches use local cues of similarity , whereas our approach attempts to optimize a global distance function .', 'There has also been theoretical work on predicting “shortcut edges” in graphs to minimize the average shortest-path distance amongst all nodes in the graph [38] or the diameter of the graph [39]–[42]; however , these works also do not exploit specific sources and targets when making predictions .', 'In this paper , we propose a combinatorial optimization framework to identify missing interactions that putatively mediate the passage of signals within pathways .', 'Formally , we seek the edges to add to the network that maximally decrease the shortest-path distances between sources and targets ( Figure 1 ) .', 'We consider several variants of the problem: an unrestricted setting where long paths are allowed; a restricted setting where source-target paths are bounded by a maximum number of hops; and a setting where each target is only required to be regulated by a single source .', 'In computational experiments using a confidence-weighted protein interaction network for S . cerevisiae under the high osmolarity glycerol ( HOG ) osmotic stress response pathway , we find that we can drastically reduce source-target distances via the addition of only a few edges .', 'Several new interactions predicted by our method , while missing from current databases , are supported by the literature; other interactions are novel predictions .', 'We selected one of our novel predictions , , for condition-specific follow-up experiments .', "New knockout microarray experiments suggest that Sok2 is indeed functionally downstream of Tpk2 in the osmotic stress response , and previous evidence suggests that this could be due to Tpk2's direct phosphorylation of Sok2 ."], ['We assume we are given a directed protein interaction network with nodes ( ) corresponding to proteins and edges ( ) to physical interactions .', 'Protein interaction networks inferred from high-throughput experiments are often noisy [2] , [43] , therefore we assume each edge is weighted by a value denoting our confidence in the interaction [13] .', 'We also assume we are given a set of sources and targets .', 'The sources are typically upstream proteins in pathways that initiate a signaling cascade to the downstream targets ( transcription factors ) .', 'Our goal is to predict missing ( directed ) edges that lie centrally “in-between” the sources and targets .', 'These edges putatively belong to the pathway but are not present in current databases .', 'Formally: Problem 1 [Shortcuts] .', 'Given a directed and weighted graph and a set of sources and targets , add edges to to minimize , i . e . the total shortest-path distance between all source-target pairs .', 'We use the shortest-path distance to measure the distance between proteins and in the weighted network ( as opposed to other distance measures , such as those based on random walks [44] , [45] ) because the shortest path represents a direct and specific series of high-likelihood signaling events .', 'The shortest path between two nodes in a weighted graph can be very long ( either because the diameter is long or if the path uses many high confidence , and hence lowly weighted , edges ) .', 'This may not be biologically reasonable since pathway targets are typically no more than 5 edges away from their closest sources [13] .', 'Thus , we also propose a hop-restricted version of our problem .', 'Let be the shortest-path distance between and that uses at most links ( if no such satisfying path exists ) .', 'Formally: Problem 2 [Shortcuts-X ( restricted ) ] .', 'Given a directed and weighted graph , a set of sources and targets , and a maximum allowable number of hops , add edges to to minimize , i . e . the total hop-restricted shortest-path distance between the pairs .', 'Both of these problems ( general and hop-restricted ) assumes that each transcription factor receives signal from each source .', 'Another variant of these problems asks to minimize the distance between each target and any single source ( biologically , the same source does not need to regulate all targets , but every target is regulated by some source ) .', 'Formally: Problem 3 [Shortcuts-SS ( single source ) ] .', 'Given a directed and weighted graph and a set of sources and targets , add edges to to minimize , i . e . the total shortest-path distance between each target and its single closest source .', 'We also consider the analogous problem in the hop-restricted setting: Problem 4 [Shortcuts-X-SS ( restricted , single source ) ] .', 'Given a directed and weighted graph , a set of sources and targets , and a maximum allowable number of hops , add edges to to minimize , i . e . the total hop-restricted shortest-path distance between each target and its single closest source .', 'In the Supporting Text ( Text S1 and Figure S1 ) we prove that these four edge predictions problems are NP-hard .', 'Given these hardness results , we consider a heuristic greedy algorithm for our suite of edge prediction problems .', 'The Greedy algorithm selects edges to add iteratively: in each step , it predicts a single edge that maximally reduces the objective function .', 'In the case of the Shortcuts problem , this means the algorithm will pick , from amongst all possible non-existent edges , the edge that maximally reduces the global shortest-path distance between all sources and targets .', 'In a network with nodes and directed edges , there are non-existent edges ( excluding self-loops ) .', 'In the yeast network we use , and , which means there are almost 20 million directed edges to test .', 'Each edge can alter the shortest path from any source to any target hence , done navely , this would require recomputing the shortest-path lengths from each source to each target 20 million times just to add a single edge .', 'One trick to make the search more efficient is to notice that , if a candidate edge reduces the distance from source to target then the new shortest path from to consists of three components: the shortest path from to , the candidate edge , and the shortest path from to .', 'If it does not reduce the distance , then the distance from to remains as it was without .', 'Thus , the procedure can be made more efficient by pre-computing the shortest-path distances from every source to every other node in the network , and separately from every node in the network to every target .', '( This latter step can be further optimized by computing the distance from every target to every other node in the reverse graph , where edge directions are reversed . )', 'To compute the cost reduction of candidate edge with weight we check if: ( 1 ) The left-hand side sums the ( pre-computed ) distance from to , the weight of the new edge , and the distance from to ; the right-hand side is the previous distance from to without the new edge .', '( If we do not know the weight of the non-existent edge we set to encourage its usage; other values , e . g . based on the predicted likelihood of the interaction that is derived from other data sources may also be reasonable ) .', 'The minimum of these two values is stored and is summed over each source-target pair , yielding the new objective function cost assuming exists in the graph .', 'The edge that maximally decreases the cost function over all possible edges is added to the graph .', 'Box 1 shows the pseudocode for the Greedy algorithm for the Shortcuts problem .', "This trick reduces the algorithm's complexity in each step from in the nave case to .", "The first term considers all possible non-existing edges , each of which requires a constant lookup ( Equation 1 ) ; the second term is the pre-computation of single-source shortest-path distances using Dijkstra's algorithm .", 'Thus , we get a runtime reduction of a factor of , which in our case is roughly 60 , 000 for each iteration .', 'For the hop-restricted problems ( Shortcuts-X and Shortcuts-X-SS ) , we seek short paths between sources and targets with the restriction that each path uses a maximum of hops .', 'This bound stems from the fact that many pathways in signaling databases such as KEGG [46] depict on average 5 edges between a target and its closest source [13] .', 'Other approaches have used similar bounds ( 3–4 [47] ) .', 'To constrain the shortest paths to use at most edges , we use a modified version of the Bellman-Ford algorithm [48] , [49] .', 'This algorithm computes single-source shortest paths starting from a node by relaxing every edge in each step ( i . e . checking if traveling along the edge yields a shorter path to the destination node ) .', 'Shortest-path distances are propagated through the graph and , as a result , after iterations , the algorithm computes the shortest-path distance from to every other node in the graph using at most hops .', 'Computing the updated cost for a candidate edge , however , requires a slightly different strategy than the one used before .', 'The main challenge is that the new edge induces one hop , and hence , the two sub-cases ( and ) must be constrained to use hops in total .', 'This leads to 6 possible cases to consider for the each candidate edge when computing the new distance from source to target , and each can be computed in constant time: ( 2 ) In the first case , the new path from to uses hop to reach , hop to reach ( via the new edge ) , and hops to reach .', 'The cost of this path consists of the Bellman-Ford distances shown ( where e . g . is the distance from to that uses at most hops ) plus the weight of the new edge ( ) .', 'Cases 2 and 3 follow similarly .', 'If either endpoint of the candidate edge involves or , then a similar rule is checked ( cases 4 and 5 ) .', 'Each case is considered and the one that yields the minimum distance is compared with the previous distance from to ( without the new edge; case 6 ) .', 'For the Shortcuts-X problem , this is repeated for each source-target pair; for Shortcuts-X-SS this is done for each target to find the hop-restricted distance to its closest source .', 'After an edge is added , the Bellman-Ford distances are re-computed ( from sources to all nodes in the graph and from targets to all nodes in the reversed graph ) and the process is repeated greedily .', 'This algorithm takes time per step .', 'The first term evaluates the benefit of each possible edge ( Equation 2 ) ; the second term is the pre-computation of single-source hop-restricted shortest-path distances using the Bellman-Ford algorithm .', 'We compare our Greedy algorithm to several other popular algorithms for predicting missing interactions .', 'Several strategies have previously been used to validate network-based edge predictions [34] , [61] .', 'First , we describe the notion of potential edges , and then we describe four validation techniques using these edges .', 'The STRING database aggregates protein-protein associations from over a dozen other pathway and protein interaction databases and combines these with computational predictions based on sequence , co-expression , literature mining , interactions between orthologous proteins , and other biological features to provide a comprehensive protein relationship resource [50] .', 'Only a small subset of these relationships , however , represent physical binding interactions .', 'The remainder , which we term potential edges , are composed of other types of experimentally- or computationally-derived non-physical associations .', 'STRING assigns edge weights for both types of edges ( physical and potential ) based on biological and computational evidence supporting the link .', 'One benefit of the STRING weighting scheme is that weights for both the physical and potential edges are computed in the same manner and thus are directly comparable .', 'Edges supported by multiple types of evidence have higher weights [62] .', 'Our predictions are based solely on the network topology and source-target connectivity — they do not rely on sequence , gene expression , or any of the other data types — and are therefore completely independent of the STRING predictions .', 'Starting from only the STRING physical interactions , one way to test our predicted edges is to count how many of them exist within the set of STRING potential edges .', 'The STRING potential network contains 659 , 719 of the approximately 20 million possible interactions ( 3 . 5% ) , hence identifying the correct interactions is still very challenging .', 'Although identifying STRING potential edges is useful , these predictions may not bear any relevance to the HOG pathway from which the sources and targets are derived .', 'Our second validation approach considers a prediction as correct if it exists within the STRING potential edges and it connects two proteins from the set of sources , targets , and other known HOG pathway members [46] , [53]; otherwise it is incorrect .', 'KEGG and the Science Signaling Database of Cell Signaling provide an unbiased set of pathway members that are not dependent on our own subjective curation efforts .', 'Although these pathway databases omit some HOG members reported in recent literature ( e . g . the upstream proteins in de Nadal and Posas [54] ) and other uncharacterized proteins that partake in the osmotic stress response , the proteins and interactions they do contain are provided by pathway experts and are thus trustworthy .', "Therefore this test serves as a strong proxy for each method's ability to make high quality and pathway-relevant predictions .", 'Our third test measures the quality of an edge prediction based on how much its addition reduces the objective function cost .', "This approach directly quantifies the method's ability to reduce the distance between sources and targets .", 'Finally , as a fourth test , we conducted the following cross-validation experiment: We started with the unoriented STRING PPI network and identified all the edges connected to at least one HOG-relevant node ( there were 1079 such edges ) .', 'Because our algorithm specifically predicts edges that lie between sources and targets , these HOG-related edges were used as the cross-validation set .', 'We performed 5-fold cross-validation for the Greedy algorithm using the Shortcuts and Shortcuts-X objective functions and counted how many of the top 10 predictions exactly recovered a left-out edge .', 'The probability that a random prediction would recover a left-out edge from amongst all the potential edges is extremely small ( 0 . 033% ) , and thus this test is also very challenging .', 'It is also challenging because it is difficult to decouple training and test sets of edges .', 'Leaving out even a very small number of edges may result in an entirely different pathway structure in which alternative paths may emerge as more likely .', 'This is especially prevalent on small scales: for example , if edges exist and the edge is left-out , then it is entirely reasonable to predict edge as a shortcut of the path chain .', 'More generally , any chain can be shortcutted by directly connecting the ends ( which may often be hubs through which the paths diverge ) , and single-use edges that play a peripheral role in the pathway may be bypassed altogether .', 'To summarize , we consider four approaches to validate edge predictions .', 'The first test compares the prediction accuracy of each method in identifying STRING potential edges .', 'The second test compares the prediction accuracy of each method when predicting STRING potential edges that are also relevant to the HOG pathway .', "The third compares each method's ability to reduce the objective function cost .", 'And the fourth measures the cross-validation accuracy of the Greedy algorithm .'], ['Our Greedy algorithm achieves the greatest cost reduction compared to the other four methods over all variants of the pathway-aware edge prediction problems ( Figure 2 ) .', 'Moreover , Greedy substantially decreased source-target distances after adding only a few edges .', 'For example , after adding 3 edges , the Shortcuts cost ( measured as the total shortest-path distance amongst source-target paths ) can be reduced to approximately 60% of the original cost .', 'In contrast , it takes 10 edges for Direct-ST to achieve the same ratio .', 'The Betweenness algorithm does monotonically decrease the cost , however , because edges are added based on greater usage ( as opposed to greater explicit cost reduction ) , its reduction is much slower than Greedy overall .', 'The global methods ( Jaccard and Short-Path ) do not leverage the sources and targets and therefore are unable to reduce source-target distances at all; in general , there are an enormous number of possible edges that play no putative role in the pathway and it is difficult for these methods to disambiguate these edges from HOG-relevant edges .', 'The tremendous cost reduction seen with the Greedy predictions implies that there are a few missing edges in the network whose addition may cover a large bulk of the information flow in the network .', 'For Shortcuts-SS and Shortcuts-X-SS , both Greedy and Direct-ST perform equally well .', 'This is because there are only 11 paths to optimize over instead of 55 ( each target to a single source ) .', 'Thus , a viable strategy is to find the target that is furthest away from any source and connect a source directly to it .', 'This can greatly reduce the cost function , even if no other path uses this edge , though this need not be the case in general .', 'Next , we judged the quality of the predictions based on how well they overlapped with the STRING potential edges and with HOG-relevant proteins ( Figure 3 ) .', 'In these tests , the accuracy of the method is the percentage of predicted edges , made from amongst all possible non-existent edges , that lied in the relevant set .', 'When only considering support in STRING ( Figure 3A ) , we find that the global methods ( Jaccard and Short-Path ) significantly outperform the source-target-based methods .', 'In particular , every prediction made by the Jaccard algorithm is correct according to STRING as are over 60% of the Short-Path predictions .', 'This result agrees with previous studies that showed that network distance and shared topology are strong indicators for functional or physical relatedness [33] , [35] , [37] , [57]–[59] .', 'The probability of predicting a STRING potential edge from amongst all possible edges is only 3 . 5% , and thus most approaches perform significantly better than baseline .', 'This test , however , does not tell us whether the predictions bear any relevance to the HOG pathway , which is the primary focus of this study .', 'To better home-in on HOG-relevant predictions , we filtered the STRING potential edges to only include those edges that connected two known HOG-related proteins .', 'Figure 3B shows that the global methods do not make any predictions that relate to the HOG pathway .', 'On the other hand , the Greedy predictions remain at the same level in both tests , which implies that its predictions tend to be highly accurate and lie amongst HOG-related nodes .', 'The difference is especially pronounced in the hop-restricted cases , where Greedy is more accurate than any other method by roughly 40% ( Shortcuts-X ) .', 'Two of these edges connect Hog1 to known HOG transcription factors , Msn4 and Cin5 — both previously established interactions in KEGG [46] or the literature [63] ( which are missing from the STRING database and thus do not appear in the original network we used ) .', 'The probability of predicting a HOG-relevant STRING potential edge from amongst all possible edges is only 0 . 076% , which is much lower than the accuracy of all three source-target-based algorithms .', 'Of the top 15 predictions made by Greedy and Betweenness for the Shortcuts-X problem , only one prediction overlaps , and a similar trend holds for the other objectives .', 'This likely stems from the fact that Greedy takes the magnitude of the cost reduction into account , whereas Betweenness only computes the number of shortest paths that use the candidate edge .', 'Because both algorithms perform significantly better than baseline , this implies that they may provide complementary predictions and both may be reasonable depending on the use case .', 'Interestingly , despite their similar performance in cost reduction for Shortcuts-SS and Shortcuts-X-SS ( Figure 2 ) , Greedy makes more accurate predictions than Direct-ST ( Figure 3 ) .', 'This is because there are many cases where a direct source-to-target prediction can be equivalently replaced by a target-target interaction .', 'For example , if was added in the first step , the predictions and ( regulated via ) both equally reduce the cost from a single source ( ) to the target .', 'However , target-target interactions are more likely to exist within the STRING potential edges than direct source-target edges , and indeed Greedy makes several TF-TF predictions ( e . g . ) , thereby giving it an advantage .', 'To show that the orientation step is indeed useful in extracting HOG paths given sources and targets , we ran each algorithm on the unoriented STRING PPI network ( Figure S2 ) .', 'We found that for both hop-restricted objective functions , the Greedy algorithm makes more HOG-relevant predictions when using the oriented network ( 53% vs . 46% for Shortcuts-X and 40% vs . 20% for Shortcuts-X-SS , compared to using the unoriented network ) .', 'Moreover , the global methods ( Short-Path and Jaccard ) also benefited significantly from the orientation , which implies that defining network neighbors more precisely can help in identifying putative interactions .', 'Overall , these results show that the global methods perform well in identifying putative interactions , but that the Greedy algorithm can home-in on more pathway-consistent interactions while drastically reducing source-target distances .', 'While predicting plausible edges from amongst all possible edges serves as a strong validation technique , in practice , we would also like to leverage other data sources ( such as expression , sequence , and literature evidence ) when making predictions .', 'To naturally integrate these sources into our framework , instead of predicting from amongst all possible edges , we only predict from amongst the set of STRING potential edges ( Methods ) .', 'Each potential edge is weighted by STRING with a confidence value in , which we explicitly set to ( Equations 1 and 2; in the previous sections , was given a default weight of 0 ) .', 'By using these data types and weights together , we can pinpoint putative interactions that have evidence from a wide variety of biological sources as well as evidence from the network .', 'Table 2 presents the top 10 predictions made by the Greedy algorithm for the Shortcuts objective function , many of which are known physical interactions missing from STRING .', 'The and predictions have direct evidence of physical interaction according to BiOGRID [64] , but were not present in the STRING network .', 'The and predictions lied within the STRING binding edges ( and thus represent physical interactions ) , but were either oriented in the opposite direction or were left out of the oriented network .', 'was originally oriented , but the Greedy algorithm suggests that that this edge was either oriented incorrectly or is bidirectional .', 'was left out of the network because the orientation algorithm did not find any length-bounded paths that included this edge .', 'Although in general biological pathways are short , this prediction exemplifies an exception where considering longer pathways through the edge improves the source-target connectivity .', 'These correct predictions demonstrate that our approach can correct for limitations of the edge orientation .', 'For the following three predictions , we verified both the physical interaction between the two nodes and the directionality ( which is not possible for edges validated with the undirected STRING or BioGRID databases ) .', 'The prediction ( ) involves two general stress TFs that play a substantial role in the HOG pathway [51] .', 'Harbison et al . [65] showed that indeed Msn4 binds the MSN2 gene in the succinic acid stress condition .', 'This study did not profile Msn4 DNA binding in osmotic stress , but it is plausible that this stress-activated TF could bind MSN2 in other conditions as well .', 'The prediction ( ) was recently shown by Pokholok et al . [63] to occur in osmotic stress .', 'We discuss the prediction ( ) at length in the next section .', 'Overall , 7 of the top 10 predictions have support for direct physical binding in the cell .', 'In addition , the prediction was not directly supported in the literature but warrants further study .', 'Both Reg1 and Msn4 have been shown to physically associate with the 14-3-3 proteins Bmh1 and Bmh2 [66] but have not yet been shown to directly interact with one another .', 'Proteins with a common physical interaction partner may be more likely to directly interact themselves than proteins with other types of functional connections ( e . g . genetic interactions ) [33] , [35] , [57] .', 'Table 3 presents the top 10 predictions made by the Greedy algorithm for the Shortcuts-X objective function , which attempts to model more biological constraints by imposing a hop-restriction on the source-target paths .', 'Remarkably , the top three predictions ( , , and ) represent best-case predictions: The two genes/proteins involved are known to physically interact , the directionality is correct , and the interaction is highly relevant to osmotic stress response .', 'In particular , and are core HOG pathway interactions that are well-characterized [51] and appear in KEGG [46] , but lack evidence for physical binding in STRING .', 'The MAPK Hog1 is central to the HOG response program , and its activation of downstream TFs is a critical component of the response .', 'The other two validated predictions involve HOG pathway members as well .', 'Sho1 is a transmembrane osmosensor , and its branch of activation of Hog1 is known to be mediated by interaction with Cdc42 [67] .', 'The interaction is also present as part of the related starvation subpathway of MAPK in KEGG [46] .', 'Finally , the prediction ( ) is between two members of the Sho1 HOG pathway input branch [53] .', "Overall , of the 659 , 719 STRING potential edges considered , only 0 . 0011% are in KEGG , and thus the fact that 3 of the top 10 predicted edges lie in KEGG is highly significant ( , Fisher's exact test ) .", 'Other predictions whose physical interaction could not be validated also involve pairs of HOG pathway members .', 'Some predictions occur between the two independent upstream input branches in the pathway ( e . g . and ) or between upstream proteins and proteins that are very far downstream ( e . g . ) .', 'From an algorithmic standpoint , these edges do indeed provide faster diffusion of signal from sources to targets; however , they may not represent direct interactions that occur in the cell .', 'In contrast , the prediction is a shortcut within the Sho1 input branch , which contains the cascade [54] .', 'Note that several of these predicted edges have very high weights ( e . g . ) from STRING reflecting their strong functional dependencies , which makes them more likely to be selected by our algorithm .', 'However , several predictions were made despite lower evidence ( e . g . ) , which suggests that their addition strongly aided source-target connectivity .', 'Interestingly , none of the top 10 predictions directly connects a source to a target .', 'This further necessitates an approach like ours versus Direct-ST .', 'To further validate our ability to extract accurate pathway-relevant predictions from within the potential set , we conducted 5-fold cross-validation experiments by leaving out HOG-relevant edges ( see Methods ) .', 'The probability that a random prediction would recover a left-out edge from amongst all the potential edges is extremely small ( 0 . 033% ) .', 'Using the Greedy algorithm , we found that 12% ( 16% ) of the top 10 predictions for Shortcuts ( Shortcuts-X ) recovered a left-out edge .', "Recovering one correct edge ( 10% ) yields a P-value of and recovering two correct edges ( 20% ) yields a P-value of ( Fisher's exact test ) .", 'Both values are significant ( our results lie between them ) further supporting the ability of our method to make accurate edge predictions .', 'To explore the sensitivity of our results to the hop-restriction length , we repeated our computational experiments using a hop-restriction length of .', 'Overall , we found similar qualitative performance for the algorithms when predicting from amongst all possible edges ( Figure S3 ) .', 'However , when predicting from amongst the potential set , we found only a few overlapping predictions with those made when the hop length was 5 .', 'Interestingly , these included the well-known HOG interactions , and , suggesting that the most confident and likely predictions are not wholly affected by the decreased hop restriction .', 'Of course , some different predictions are also to be expected; for example , using a hop length of 4 , the algorithm makes predictions for and .', 'While these predictions make sense algorithmically , they do not make sense biologically because they attempt
['Introduction', 'Methods', 'Results', 'Discussion']
['Embedded within large-scale protein interaction networks are signaling pathways that encode response cascades in the cell .', 'Unfortunately , even for well-studied species like S . cerevisiae , only a fraction of all true protein interactions are known , which makes it difficult to reason about the exact flow of signals and the corresponding causal relations in the network .', 'To help address this problem , we introduce a framework for predicting new interactions that aid connectivity between upstream proteins ( sources ) and downstream transcription factors ( targets ) of a particular pathway .', 'Our algorithms attempt to globally minimize the distance between sources and targets by finding a small set of shortcut edges to add to the network .', 'Unlike existing algorithms for predicting general protein interactions , by focusing on proteins involved in specific responses our approach homes-in on pathway-consistent interactions .', 'We applied our method to extend pathways in osmotic stress response in yeast and identified several missing interactions , some of which are supported by published reports .', 'We also performed experiments that support a novel interaction not previously reported .', 'Our framework is general and may be applicable to edge prediction problems in other domains .']
['Networks of protein interactions encode a variety of molecular processes occurring in the cell .', 'Embedded within these networks are important subnetworks called signaling pathways .', 'Pathways are initiated by upstream proteins ( called sources ) that receive signals from the environment and trigger a cascade of information to downstream proteins ( targets ) .', 'Modeling the interactions that occur within this cascade is important because pathway disruption has been linked to several diseases .', 'Further , the interactions help us better understand how cells respond to various conditions and environments .', 'Unfortunately , interaction networks today are largely incomplete , which makes this analysis difficult .', 'We provide a framework to model missing interactions in pathways by searching for interactions that putatively result in quicker and more efficient source-target cascades .', 'We find that we can substantially shorten source-target distances with only a few additional edges and that many of our predicted edges have support in several knowledge databases and literature reports .', 'We believe our approach will be useful to identify interesting and important pathway-centric interactions that have been missed by previous experimental assays .']
['algorithms', 'systems biology', 'computer science', 'signaling networks', 'biology', 'computational biology']