Finding undetected protein associations in cell signaling by belief propagation

Introduction

• The approach combines expression evidence with reliable interaction data to help reveal unknown interactions, motivating efficient heuristics that handle varying interaction reliability and alternative paths.A parameter weights expression data relative to interaction data or established pathway knowledge.Source: Introduction · p. 1
• The method infers a functional network as a connected subgraph of the full protein-interaction network, rather than aggregating separately identified pathways as earlier works do.The paper presents a complete description of the approach, including algorithmic and experimental validations.Source: Introduction · p. 1
• The PCST formulation selects a connected subgraph by balancing positive edge costs against vertex prizes; edge costs reflect interaction confidence, prizes are −log p-values of differential expression, and λ controls subgraph size.The graph represents the protein-interaction network, with edges assigned costs and vertices assigned prizes.Source: Introduction · pp. 1–2
• The optimization is NP-hard even when vertex prizes are restricted to {0, L} for large L, making heuristic algorithms necessary for instances from large datasets.That limiting case corresponds to the also NP-hard Minimum Steiner Tree problem.Source: Introduction · p. 2
• The authors report that computational cost scales roughly linearly with problem size and that the algorithm is fully parallelizable; its performance gap over LP-based methods increases with problem size.These properties suggest suitability for problems defined on large networks.Source: Introduction · p. 2

• Generalizing the statistical-physics analysis in, minimizing the cost selects connected networks with reliable edges and significantly differentially expressed nodes; the scheme can incorporate knockout data and biological priors.Source: A Message-Passing algorithm for PCST · p. 2
• An extra variable for each node encodes its visit time from a root, making the global connectivity condition expressible as local constraints while preserving one-to-one correspondence with connected subgraphs.Source: A Message-Passing algorithm for PCST · p. 2
• Iterative message passing solves efficient functional equations estimating each link’s probability of belonging to an optimal subgraph at a given root distance; optimality holds in certain limits, and code is available.Source: A Message-Passing algorithm for PCST · p. 2

Tests and data analysis

• The algorithm improved the best-known costs for almost all open SteinLib MSTT benchmarks in a fraction of the computational time.The benchmarks are large, difficult, and non-biological; direct comparisons also suggest LP-based methods become highly inefficient on moderate-sized networks.Source: Tests and data analysis · p. 2
• On biological data, the algorithm found essentially the same pathways as the color-coding method more efficiently, with computational cost growing linearly rather than exponentially with chain length.Adjusting chain length recovered pathway variability.Source: Tests and data analysis · p. 2

Pheromone response data

• The pheromone analysis used 56 expression datasets and a fused MIPS-DIP yeast protein network, inferred sub-networks across λ values, and rooted the trees at STE2.Results from the expression patterns were merged into a frequency-weighted network, with directions toward the chosen root.Source: Tests and data analysis · p. 3
• The inferred network recovered known pheromone-response branches and included stable-expression Steiner proteins that may connect signaling modules and are detectable through combined interaction and transcriptomics data.Branches included cell-cycle, cell-polarity/cytoskeleton, and PRM, sphingolipid-synthesis, and cell-wall proteins; neighboring proteins shared GO Slim annotations more often than in random trees (t-test, p < 5.10−7).Source: Tests and data analysis · p. 3
• COS8 appeared frequently enough in bootstrap tests to be significant, and its inferred interactors suggested an endoplasmic-reticulum role in sphingolipid synthesis, consistent with its detection under TOR-inhibiting stress.The pheromone analysis linked COS8 to the STE2-GPA1-SST2-SHO1 cascade; the caffeine/rapamycin analysis also detected COS8 as a Steiner protein, significantly enriched with the same interacting partners.Source: Tests and data analysis · p. 3

Experimental validation.

• COS8 deletion rescued rapamycin- and caffeine-associated phenotypes of ∆FEN1 and ∆YCR061W strains and partially rescued ∆SUR4, while COS8 overexpression caused caffeine hypersensitivity.The overexpression phenotype matched FEN1 deletion; the authors also observed a genetic interaction with IRE1, COS8’s annotated role [29].Source: Experimental validation · p. 4
• After 36 hours in 0.1 mM myriocin, ∆COS8 cells showed a transient growth benefit, consistent with COS8 negatively regulating VLCFA elongation and sphingolipid production.A weak but reproducible increase in myriocin resistance was also observed on solid YPD media.Source: Experimental validation · p. 4

Discussion

• The discussion links sphingolipid synthesis, particularly ceramide, with pheromone response and TOR signaling, noting that TOR activates ceramide synthesis from dihydrosphingosine [34, 35].The molecular mechanism remains unknown; the authors regard this connection as consistent with their findings on COS8’s negative role in VLCFA elongation.Source: Discussion · p. 4

Conclusions

• The algorithm achieved better optima than previously known on unsolved SteinLib instances, outperforming the field’s best-known techniques.The authors also report a direct comparison with LP-based techniques in the full methods materials.Source: Conclusions · p. 4
• COS8 was predicted to function in sphingolipid synthesis and the TOR pathway, and experiments showed its involvement in a regulatory loop at ceramide synthesis.COS8 belongs to a large gene family whose functional role was previously unknown.Source: Conclusions · p. 4
• The technique extracts candidate signaling networks by optimizing graphs built from gene-expression and protein-protein interaction data, and can suggest roles for proteins of unknown function.The authors describe it as efficient, with nearly linear time complexity, simple fixed-point equations, and parallelizability.Source: Conclusions · p. 4
• The method can incorporate biological priors such as synthetic-lethal interactions or phosphoproteomics and is adaptable to many network-reconstruction problems in systems biology.The authors identify these capabilities as reasons the technique may be valuable for a broad class of optimization problems.Source: Conclusions · p. 4