Finding undetected protein associations in cell signaling by belief propagation
arXiv:1101.4573 · doi:10.1073/pnas.1004751108
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.
arXiv comment6 pages, 3 figures, 1 table, Supporting Information
References in corpus (3)
Cited by in corpus (15)
- Vital nodes identification in complex networks
- Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
- Containing epidemic outbreaks by message-passing techniques
- Spin glass approach to the feedback vertex set problem
- Optimizing spread dynamics on graphs by message passing
- Large deviations of cascade processes on graphs
- A Max-Sum algorithm for training discrete neural networks
- On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
- Efficient Minimax Signal Detection on Graphs
- Theory and learning protocols for the material tempotron model
- Cavity approach to sphere packing in Hamming space
- The cavity approach for Steiner trees packing problems
- Density-Based Region Search with Arbitrary Shape for Object Localization
- Practical optimization of Steiner Trees via the cavity method
- A cavity approach to optimization and inverse dynamical problems