Finding undetected protein associations in cell signaling by belief propagation

Abstract

External information propagates in the cell mainly through signaling cascades and transcriptional activation, allowing it to react to a wide spectrum of environmental changes. High-throughput experiments identify numerous molecular components of such cascades that may, however, interact through unknown partners. Some of them may be detected using data coming from the integration of a protein-protein interaction network and mRNA expression profiles. This inference problem can be mapped onto the problem of finding appropriate optimal connected subgraphs of a network defined by these datasets. The optimization procedure turns out to be computationally intractable in general. Here we present a new distributed algorithm for this task, inspired from statistical physics, and apply this scheme to alpha factor and drug perturbations data in yeast. We identify the role of the COS8 protein, a member of a gene family of previously unknown function, and validate the results by genetic experiments. The algorithm we present is specially suited for very large datasets, can run in parallel, and can be adapted to other problems in systems biology. On renowned benchmarks it outperforms other algorithms in the field.

Fig. 1.

An example of a prize-collecting Steiner tree. Larger nodes mean larger prizes; thickness of the edges is proportional to their cost. A prize-collecting minimum Steiner tree (right) picks as many as possible of the larger nodes while simultaneously picking the thinnest links and maintaining connectivity. The analyzed yeast protein network has approximately 5,000 nodes and 22,000 edges.

Fig. 2.

This graph is a subnetwork of the protein–protein interaction map, obtained by including nodes that appear more than 30% of the time on the 56 inferred Steiner trees for λ = 0.2, with link intensity proportional to the number of times the specific connection was found and node size proportional to average prize. The layout was decided in order to minimize crossings with the Graphviz suite. Afterwards, colors were added denoting the main GO annotation: actin (light green), cell cycle (yellow), chromatin structure (blue), spindle checkpoint (dark green), cell wall (cyan), and pheromone sensing (magenta). The annotations were obtained from the SGD project Saccharomyces Genome Database http://www.yeastgenome.org/.

Fig. 3.

(A) The main proteins interacting with COS8 in our signaling tree. Squares stand for membrane proteins. The dotted lines show that many protein interactions are never found in our tree. (B) A global scheme of the putative negative regulatory role of COS8, at the interface between very long chain fatty acid elongation (VLFCA), TOR signaling, and the unfolded protein response (see text). (C) A subset of the genetic experiments showing (i) the rescue of ΔYCR061W, ΔSUR4, ΔFEN1, and ΔIRE1 by ΔCOS8 in rapamycin medium; (ii) the effects of either the disruption or the overexpression of COS8 in a caffeine medium.