Limits...
Discovering pathways by orienting edges in protein interaction networks.

Gitter A, Klein-Seetharaman J, Gupta A, Bar-Joseph Z - Nucleic Acids Res. (2010)

Bottom Line: Expression and knockdown studies can determine the downstream effects of these interactions.The discovered paths match several known signaling pathways and suggest new mechanisms that are not currently present in signaling databases.For some pathways, including the pheromone signaling pathway and the high-osmolarity glycerol pathway, our method suggests interesting and novel components that extend current annotations.

View Article: PubMed Central - PubMed

Affiliation: Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA.

ABSTRACT
Modern experimental technology enables the identification of the sensory proteins that interact with the cells' environment or various pathogens. Expression and knockdown studies can determine the downstream effects of these interactions. However, when attempting to reconstruct the signaling networks and pathways between these sources and targets, one faces a substantial challenge. Although pathways are directed, high-throughput protein interaction data are undirected. In order to utilize the available data, we need methods that can orient protein interaction edges and discover high-confidence pathways that explain the observed experimental outcomes. We formalize the orientation problem in weighted protein interaction graphs as an optimization problem and present three approximation algorithms based on either weighted Boolean satisfiability solvers or probabilistic assignments. We use these algorithms to identify pathways in yeast. Our approach recovers twice as many known signaling cascades as a recent unoriented signaling pathway prediction technique and over 13 times as many as an existing network orientation algorithm. The discovered paths match several known signaling pathways and suggest new mechanisms that are not currently present in signaling databases. For some pathways, including the pheromone signaling pathway and the high-osmolarity glycerol pathway, our method suggests interesting and novel components that extend current annotations.

Show MeSH
Fraction of the objective function upper bound achieved on instances with simulated sources and targets. After local search, all approximation algorithms perform much better than the MAX-k-CSP theoretical guarantee on instances with simulated source–target pairs and find orientations whose objective function values are virtually indistinguishable. The number of undirected paths includes all paths from a source to a target before the network is oriented. The y-axis plots the ratio achieved by each algorithm, which is the score of the orientation returned by the algorithm divided by the upper bound on the optimal objective function value. For each instance, there are six points (one for each algorithm with and without local search) that have the same x-coordinate, the number of undirected paths, and different y-coordinates, the ratios achieved. Instances have been ordered along the x-axis by the number of distinct source–target paths in the network before orientation, which is a coarse indication of the difficulty of the instance.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3045580&req=5

Figure 3: Fraction of the objective function upper bound achieved on instances with simulated sources and targets. After local search, all approximation algorithms perform much better than the MAX-k-CSP theoretical guarantee on instances with simulated source–target pairs and find orientations whose objective function values are virtually indistinguishable. The number of undirected paths includes all paths from a source to a target before the network is oriented. The y-axis plots the ratio achieved by each algorithm, which is the score of the orientation returned by the algorithm divided by the upper bound on the optimal objective function value. For each instance, there are six points (one for each algorithm with and without local search) that have the same x-coordinate, the number of undirected paths, and different y-coordinates, the ratios achieved. Instances have been ordered along the x-axis by the number of distinct source–target paths in the network before orientation, which is a coarse indication of the difficulty of the instance.

Mentions: Figure 3 shows the fraction of the upper bound achieved by the algorithms on instances with simulated sources and targets (MTO and the unoriented edge selection algorithm do not use the MEO objective function and are therefore not included in this evaluation). Note that even for a fixed number of sources and targets, the number of possible paths in the network varies greatly due to network topology.Figure 3.


Discovering pathways by orienting edges in protein interaction networks.

Gitter A, Klein-Seetharaman J, Gupta A, Bar-Joseph Z - Nucleic Acids Res. (2010)

Fraction of the objective function upper bound achieved on instances with simulated sources and targets. After local search, all approximation algorithms perform much better than the MAX-k-CSP theoretical guarantee on instances with simulated source–target pairs and find orientations whose objective function values are virtually indistinguishable. The number of undirected paths includes all paths from a source to a target before the network is oriented. The y-axis plots the ratio achieved by each algorithm, which is the score of the orientation returned by the algorithm divided by the upper bound on the optimal objective function value. For each instance, there are six points (one for each algorithm with and without local search) that have the same x-coordinate, the number of undirected paths, and different y-coordinates, the ratios achieved. Instances have been ordered along the x-axis by the number of distinct source–target paths in the network before orientation, which is a coarse indication of the difficulty of the instance.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3045580&req=5

Figure 3: Fraction of the objective function upper bound achieved on instances with simulated sources and targets. After local search, all approximation algorithms perform much better than the MAX-k-CSP theoretical guarantee on instances with simulated source–target pairs and find orientations whose objective function values are virtually indistinguishable. The number of undirected paths includes all paths from a source to a target before the network is oriented. The y-axis plots the ratio achieved by each algorithm, which is the score of the orientation returned by the algorithm divided by the upper bound on the optimal objective function value. For each instance, there are six points (one for each algorithm with and without local search) that have the same x-coordinate, the number of undirected paths, and different y-coordinates, the ratios achieved. Instances have been ordered along the x-axis by the number of distinct source–target paths in the network before orientation, which is a coarse indication of the difficulty of the instance.
Mentions: Figure 3 shows the fraction of the upper bound achieved by the algorithms on instances with simulated sources and targets (MTO and the unoriented edge selection algorithm do not use the MEO objective function and are therefore not included in this evaluation). Note that even for a fixed number of sources and targets, the number of possible paths in the network varies greatly due to network topology.Figure 3.

Bottom Line: Expression and knockdown studies can determine the downstream effects of these interactions.The discovered paths match several known signaling pathways and suggest new mechanisms that are not currently present in signaling databases.For some pathways, including the pheromone signaling pathway and the high-osmolarity glycerol pathway, our method suggests interesting and novel components that extend current annotations.

View Article: PubMed Central - PubMed

Affiliation: Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA.

ABSTRACT
Modern experimental technology enables the identification of the sensory proteins that interact with the cells' environment or various pathogens. Expression and knockdown studies can determine the downstream effects of these interactions. However, when attempting to reconstruct the signaling networks and pathways between these sources and targets, one faces a substantial challenge. Although pathways are directed, high-throughput protein interaction data are undirected. In order to utilize the available data, we need methods that can orient protein interaction edges and discover high-confidence pathways that explain the observed experimental outcomes. We formalize the orientation problem in weighted protein interaction graphs as an optimization problem and present three approximation algorithms based on either weighted Boolean satisfiability solvers or probabilistic assignments. We use these algorithms to identify pathways in yeast. Our approach recovers twice as many known signaling cascades as a recent unoriented signaling pathway prediction technique and over 13 times as many as an existing network orientation algorithm. The discovered paths match several known signaling pathways and suggest new mechanisms that are not currently present in signaling databases. For some pathways, including the pheromone signaling pathway and the high-osmolarity glycerol pathway, our method suggests interesting and novel components that extend current annotations.

Show MeSH