Identifying functional modules in protein–protein interaction networks: an integrated exact approach
By Marcus T. Dittrich, Gunnar W. Klau, Andreas Rosenwald, Thomas Dandekar, T. Müller. Intelligent Systems in Molecular Biology, 2008
551 citations recorded by the source corpus.
Motivation: With the exponential growth of expression and protein–protein interaction (PPI) data, the frontier of research in systems biology shifts more and more to the integrated analysis of these large datasets. Of particular interest is the identification of functional modules in PPI networks, sharing common cellular function beyond the scope of classical pathways, by means of detecting differentially expressed regions in PPI networks. This requires on the one hand an adequate scoring of the nodes in the network to be identified and on the other hand the availability of an effective algorithm to find the maximally scoring network regions. Various heuristic approaches have been proposed in the literature. Results: Here we present the first exact solution for this problem, which is based on integer-linear programming and its connection to the well-known prize-collecting Steiner tree problem from Operations Research. Despite the NP-hardness of the underlying combinatorial problem, our method typically computes provably optimal subnetworks in large PPI networks in a few minutes. An essential ingredient of our approach is a scoring function defined on network nodes. We propose a new additive score with two desirable properties: (i) it is scalable by a statistically interpretable parameter and (ii) it allows a smooth integration of data from various sources. We apply our method to a well-established lymphoma microarray dataset in combination with associated survival data and the large interaction network of HPRD to identify functional modules by computing optimal-scoring subnetworks. In particular, we find a functional interaction module associated with proliferation over-expressed in the aggressive ABC subtype as well as modules derived from non-malignant by-stander cells. Availability: Our software is available freely for non-commercial purposes at http://www.planet-lisa.net. Contact: tobias.mueller@biozentrum.uni-wuerzburg.de
Subfields: Cell Biology, Molecular Biology
View Paper: https://www.semanticscholar.org/paper/220a896b8aa7dc658d73592b0279cf3378c76bb7
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Cell Biology
In Molecular Biology
Citations in the corpus
- Predicting Network Activity from High Throughput Metabolomics (2013, unknown): “mass flow balance of metabolic reactions [22,68].”
- pathfindR: An R Package for Comprehensive Identification of Enriched Pathways in Omics Data Through Active Subnetworks (2019, methodology): “…al., 2002; Guo et al., 2007), genetic algorithms (Klammer et al., 2010; Ma et al., 2011; Wu et al., 2011; Amgalan and Lee, 2014; Ozisik et al., 2017), and mathematical programming-based methods (Dittrich et al., 2008; Zhao et al., 2008; Qiu et al., 2009; Backes et al., 2012; Beisser et al., 2012).”
- Identifying protein interaction subnetworks by a bagging Markov random field-based method (2012, methodology): “For comparison, we also applied jActiveModules as proposed in (14), HEINZ (13) and Chuang et al.”