A network-based approach for predicting missing pathway interactions

Abstract

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.

Figure 1. Overview of our approach.

A) Example input network with sources, targets, and undirected edges. Each edge is given a weight (lower values indicate higher confidence). The total distance from each source to each target is 2.0. B) The corresponding oriented network. Nodes and edges that do not lie within a path of hops from any source-target pair are purged (shown dashed in A). The red arrow indicates an edge prediction () that globally minimizes the distance between each source and target using the Shortcuts objective function. The new distance is 1.2. C) The corresponding example using the Shortcuts-X objective function with . Here, the total hop-restricted distance between each source and target is higher (4.4) and the optimal edge, reduces the distance to 1.6.

Figure 2. The cost reduction achieved by the five methods for each objective function.

The shows the number of edges added, and the shows the new objective function cost as a percent of the original cost. Each new edge was added with weight 0.0. For Shortcuts and Shortcuts-X, Greedy significantly outperforms all other methods. For Shortcuts-SS and Shortcuts-X-SS, both Greedy and Direct-ST perform equally. As expected, the global methods (Jaccard and Short-Path) select HOG-independent edges that do not reduce any source-target distances.

Figure 3. The prediction accuracy of the five methods for each objective function.

We evaluated the top 15 (Shortcuts and Shortcuts-X) or 10 (Shortcuts-SS and Shortcuts-X-SS) predictions for each algorithm, after which the Greedy algorithm had reduced the objective function to nearly zero. The shows the prediction accuracy, defined as the percentage of predictions (from amongst all million possible missing edges) that lied within the set of A) STRING potential edges, and B) STRING potential edges that also connected known HOG-related proteins. The global methods (Jaccard and Short-Path) make accurate predictions when not constrained to be HOG-relevant. The Greedy algorithm outperforms all methods in making high quality predictions that connect HOG proteins.