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
The top-ranked pathways discovered by the random orientation plus local search algorithm. Solid edges were present in the gold standard and dashed edges were absent or oriented in the opposite direction. (A) Pathways that are completely contained within a known gold standard pathway. (B) Pathways that partially overlap a gold standard path but contain new edges as well. (C) Pathways that do not have any edges in common with our set of gold standard pathways. Images were generated with Cytoscape (http://www.cytoscape.org/) and do not contain all of the top-ranked paths per category but rather a highly overlapping subset.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 4: The top-ranked pathways discovered by the random orientation plus local search algorithm. Solid edges were present in the gold standard and dashed edges were absent or oriented in the opposite direction. (A) Pathways that are completely contained within a known gold standard pathway. (B) Pathways that partially overlap a gold standard path but contain new edges as well. (C) Pathways that do not have any edges in common with our set of gold standard pathways. Images were generated with Cytoscape (http://www.cytoscape.org/) and do not contain all of the top-ranked paths per category but rather a highly overlapping subset.

Mentions: Given the success of the methods in recovering known pathways, we asked whether the novel pathways that ranked highly according to our criteria may also be correct and represent information that is missing from current databases. We divided the pathways predicted by our random orientation with local search algorithm into three groups and analyzed the top 20 pathways in each group using the path weight for ranking. The first (Figure 4A) contains pathways of five or six proteins that were present, in their entirety, in the signaling databases. The second (Figure 4B) are pathways predicted by our method that consist of exactly six proteins and partially overlap a known pathway. For these we asked whether the additional interactions may represent known or sensible extensions to the pathway that were not previously known or were not recorded in the databases. The third (Figure 4C) are pathways discovered by our method that do not match any known pathways in the databases. For these we asked whether they represent known pathways not in the databases or novel hypotheses that make sense biologically.Figure 4.


Discovering pathways by orienting edges in protein interaction networks.

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

The top-ranked pathways discovered by the random orientation plus local search algorithm. Solid edges were present in the gold standard and dashed edges were absent or oriented in the opposite direction. (A) Pathways that are completely contained within a known gold standard pathway. (B) Pathways that partially overlap a gold standard path but contain new edges as well. (C) Pathways that do not have any edges in common with our set of gold standard pathways. Images were generated with Cytoscape (http://www.cytoscape.org/) and do not contain all of the top-ranked paths per category but rather a highly overlapping subset.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 4: The top-ranked pathways discovered by the random orientation plus local search algorithm. Solid edges were present in the gold standard and dashed edges were absent or oriented in the opposite direction. (A) Pathways that are completely contained within a known gold standard pathway. (B) Pathways that partially overlap a gold standard path but contain new edges as well. (C) Pathways that do not have any edges in common with our set of gold standard pathways. Images were generated with Cytoscape (http://www.cytoscape.org/) and do not contain all of the top-ranked paths per category but rather a highly overlapping subset.
Mentions: Given the success of the methods in recovering known pathways, we asked whether the novel pathways that ranked highly according to our criteria may also be correct and represent information that is missing from current databases. We divided the pathways predicted by our random orientation with local search algorithm into three groups and analyzed the top 20 pathways in each group using the path weight for ranking. The first (Figure 4A) contains pathways of five or six proteins that were present, in their entirety, in the signaling databases. The second (Figure 4B) are pathways predicted by our method that consist of exactly six proteins and partially overlap a known pathway. For these we asked whether the additional interactions may represent known or sensible extensions to the pathway that were not previously known or were not recorded in the databases. The third (Figure 4C) are pathways discovered by our method that do not match any known pathways in the databases. For these we asked whether they represent known pathways not in the databases or novel hypotheses that make sense biologically.Figure 4.

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