PathFinder: mining signal transduction pathway segments from protein-protein interaction networks

Abstract

Background: A Signal transduction pathway is the chain of processes by which a cell converts an extracellular signal into a response. In most unicellular organisms, the number of signal transduction pathways influences the number of ways the cell can react and respond to the environment. Discovering signal transduction pathways is an arduous problem, even with the use of systematic genomic, proteomic and metabolomic technologies. These techniques lead to an enormous amount of data and how to interpret and process this data becomes a challenging computational problem.

Results: In this study we present a new framework for identifying signaling pathways in protein-protein interaction networks. Our goal is to find biologically significant pathway segments in a given interaction network. Currently, protein-protein interaction data has excessive amount of noise, e.g., false positive and false negative interactions. First, we eliminate false positives in the protein-protein interaction network by integrating the network with microarray expression profiles, protein subcellular localization and sequence information. In addition, protein families are used to repair false negative interactions. Then the characteristics of known signal transduction pathways and their functional annotations are extracted in the form of association rules.

Conclusion: Given a pair of starting and ending proteins, our methodology returns candidate pathway segments between these two proteins with possible missing links (recovered false negatives). In our study, S. cerevisiae (yeast) data is used to demonstrate the effectiveness of our method.

Figure 1

The MAP kinase pathways. The MAP kinase pathways downloaded from the KEGG database [30].

Figure 2

Two interacting proteins, P₁ and P₂, with their respective annotation terms. An annotation link is created by linking an annotation from the first protein's annotation set to another annotation of the second protein. Above, the tuples {(a₁, a₂), (a₁, a₄), (a₂, a₂), (a₂, a₄), (a₃, a₂), (a₃, a₄)} are shown. There are a total of 3 × 2 = 6 annotation links between P₁ and P₂.

Figure 3

Association rules in Sln1-Hog1 segment. High Osmolarity Pathway Sln1-Hog1 Segment and the association rules on this pathway segment are shown. For each protein only GO [29] terms that are in an association rule are drawn. The number of GO terms each protein has are given below each protein.

Figure 4

The pheromone response signaling pathway. (A) The main chain of the pheromone pathway downloaded from KEGG, (B) the output of our PathFinder implementation, (C) The color-coding algorithm output for the pheromone pathway [20], (D) the NetSearch program prediction for the pheromone pathway [18]. The interactions that do not exist in the PPIN are shown with dashed edges in (A). Notice that, for (B),(C) and (D) the proteins that were not on the main chain of the pathway, as shown in (A), were not colored.

Figure 5

The filamentation signaling pathway. (A) The main chain of the filamentation pathway (KEGG Database), (B) PathFinder output for the Sho1-Tec1 pair (75% recall, 17% precision). For (A), the dashed interactions indicate that these interactions do not exists in the database. For (B), the proteins that were not on the main chain of the pathway were not colored, whereas the proteins on the main chain are colored grey. Proteins that are part of other pathways are colored with different colors.

Figure 6

The filamentation signaling pathway recovered completely. (A) The main chain of the filamentation pathway (KEGG Database), (B) PathFinder output for Sho1-Tec1 pair (100% recall, 12% precision). For (A), the dashed links indicate interactions that do not exists in the database. For (B), the interactions that were predicted as false negatives were shown with dashed lines. The proteins that were not on the main chain of any pathway were not colored, whereas proteins that are part of other pathways were colored.