{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T09:01:51Z","timestamp":1777885311945,"version":"3.51.4"},"reference-count":33,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":3015,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: With the exponential growth of expression and protein\u2013protein 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.<\/jats:p>\n               <jats:p>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.<\/jats:p>\n               <jats:p>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.<\/jats:p>\n               <jats:p>Availability: Our software is available freely for non-commercial purposes at http:\/\/www.planet-lisa.net.<\/jats:p>\n               <jats:p>Contact: \u00a0tobias.mueller@biozentrum.uni-wuerzburg.de<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn161","type":"journal-article","created":{"date-parts":[[2008,6,27]],"date-time":"2008-06-27T07:43:13Z","timestamp":1214552593000},"page":"i223-i231","source":"Crossref","is-referenced-by-count":416,"title":["Identifying functional modules in protein\u2013protein interaction networks: an integrated exact approach"],"prefix":"10.1093","volume":"24","author":[{"given":"Marcus T.","family":"Dittrich","sequence":"first","affiliation":[{"name":"1 Department of Bioinformatics, Biocenter, University of W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, 2Institute of Clinical Biochemistry, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, 3Mathematics in Life Sciences Group, Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Arnimallee 3, 14195 Berlin, 4DFG Research Center Matheon, Berlin and 5Institute of Pathology, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, Germany"},{"name":"1 Department of Bioinformatics, Biocenter, University of W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, 2Institute of Clinical Biochemistry, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, 3Mathematics in Life Sciences Group, Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Arnimallee 3, 14195 Berlin, 4DFG Research Center Matheon, Berlin and 5Institute of Pathology, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gunnar W.","family":"Klau","sequence":"additional","affiliation":[{"name":"1 Department of Bioinformatics, Biocenter, University of W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, 2Institute of Clinical Biochemistry, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, 3Mathematics in Life Sciences Group, Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Arnimallee 3, 14195 Berlin, 4DFG Research Center Matheon, Berlin and 5Institute of Pathology, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, Germany"},{"name":"1 Department of Bioinformatics, Biocenter, University of W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, 2Institute of Clinical Biochemistry, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, 3Mathematics in Life Sciences Group, Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Arnimallee 3, 14195 Berlin, 4DFG Research Center Matheon, Berlin and 5Institute of Pathology, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Rosenwald","sequence":"additional","affiliation":[{"name":"1 Department of Bioinformatics, Biocenter, University of W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, 2Institute of Clinical Biochemistry, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, 3Mathematics in Life Sciences Group, Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Arnimallee 3, 14195 Berlin, 4DFG Research Center Matheon, Berlin and 5Institute of Pathology, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Dandekar","sequence":"additional","affiliation":[{"name":"1 Department of Bioinformatics, Biocenter, University of W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, 2Institute of Clinical Biochemistry, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, 3Mathematics in Life Sciences Group, Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Arnimallee 3, 14195 Berlin, 4DFG Research Center Matheon, Berlin and 5Institute of Pathology, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"M\u00fcller","sequence":"additional","affiliation":[{"name":"1 Department of Bioinformatics, Biocenter, University of W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, 2Institute of Clinical Biochemistry, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, 3Mathematics in Life Sciences Group, Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, Arnimallee 3, 14195 Berlin, 4DFG Research Center Matheon, Berlin and 5Institute of Pathology, University of W\u00fcrzburg, Josef-Schneider-Str. 2, 97080 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"2023020210383172000_B1","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1093\/bib\/bbl022","article-title":"Graph-based methods for analysing networks in cell biology","volume":"7","author":"Aittokallio","year":"2006","journal-title":"Brief. Bioinform."},{"key":"2023020210383172000_B2","doi-asserted-by":"crossref","first-page":"1100","DOI":"10.1214\/aos\/1176345976","article-title":"Cox's regression model for counting processes: a large sample study","volume":"10","author":"Andersen","year":"1982","journal-title":"Ann. Stat."},{"key":"2023020210383172000_B3","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1177\/117693510700300004","article-title":"Germinal center B cell-like (GCB) and activated B cell-like (ABC) type of diffuse large B cell lymphoma (DLBCL): analysis of molecular predictors, signatures, cell cycle state and patient survival","volume":"3","author":"Blenk","year":"2007","journal-title":"Cancer Inform."},{"key":"2023020210383172000_B4","doi-asserted-by":"crossref","first-page":"1190","DOI":"10.1137\/0916069","article-title":"A limited memory algorithm for bound constrained optimization","volume":"16","author":"Byrd","year":"1995","journal-title":"SIAM J. Sci. Comput."},{"key":"2023020210383172000_B5","doi-asserted-by":"crossref","first-page":"2898","DOI":"10.1093\/bioinformatics\/bti440","article-title":"Differential network expression during drug and stress response","volume":"21","author":"Cabusora","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020210383172000_B6","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1093\/bioinformatics\/bth458","article-title":"Network structures and algorithms in Bioconductor","volume":"21","author":"Carey","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020210383172000_B7","doi-asserted-by":"crossref","first-page":"2366","DOI":"10.1038\/nprot.2007.324","article-title":"Integration of biological networks and gene expression data using Cytoscape","volume":"2","author":"Cline","year":"2007","journal-title":"Nat. Protoc"},{"key":"2023020210383172000_B8","first-page":"30","article-title":"Combining independent tests of significance","volume":"2","author":"Fisher","year":"1948","journal-title":"Am. Stat"},{"key":"2023020210383172000_B9","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1101\/gr.5235706","article-title":"Graemlin: general and robust alignment of multiple large interaction networks","volume":"16","author":"Flannick","year":"2006","journal-title":"Genome Res."},{"key":"2023020210383172000_B10","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1126\/science.1094068","article-title":"Inferring cellular networks using probabilistic graphical models","volume":"303","author":"Friedman","year":"2004","journal-title":"Science"},{"key":"2023020210383172000_B11","doi-asserted-by":"crossref","first-page":"R80","DOI":"10.1186\/gb-2004-5-10-r80","article-title":"Bioconductor: open software development for computational biology and bioinformatics","volume":"5","author":"Gentleman","year":"2004","journal-title":"Genome Biol"},{"key":"2023020210383172000_B12","doi-asserted-by":"crossref","first-page":"2121","DOI":"10.1093\/bioinformatics\/btm294","article-title":"Edge-based scoring and searching method for identifying condition-responsive protein-protein interaction sub-network","volume":"23","author":"Guo","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020210383172000_B13","doi-asserted-by":"crossref","first-page":"S233","DOI":"10.1093\/bioinformatics\/18.suppl_1.S233","article-title":"Discovering regulatory and signalling circuits in molecular interaction networks","volume":"18","author":"Ideker","year":"2002","journal-title":"Bioinformatics"},{"key":"2023020210383172000_B14","doi-asserted-by":"crossref","first-page":"11394","DOI":"10.1073\/pnas.1534710100","article-title":"Conserved pathways within bacteria and yeast as revealed by global protein network alignment","volume":"100","author":"Kelley","year":"2003","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020210383172000_B15","volume-title":"Statistical Theory","author":"Lindgren","year":"1993"},{"key":"2023020210383172000_B16","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/s10107-005-0660-x","article-title":"An algorithmic framework for the exact solution of the prize-collecting steiner tree problem","volume":"105","author":"Ljubi\u0107","year":"2006","journal-title":"Math. Program. Ser. B"},{"issue":"Database issue","key":"2023020210383172000_B17","doi-asserted-by":"crossref","first-page":"D411","DOI":"10.1093\/nar\/gkj141","article-title":"Human protein reference database\u20132006 update","volume":"34","author":"Mishra","year":"2006","journal-title":"Nucleic Acids Res"},{"key":"2023020210383172000_B18","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1093\/bioinformatics\/btm019","article-title":"Gene expression network analysis and applications to immunology","volume":"23","author":"Nacu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020210383172000_B19","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"Nemhauser","year":"1988"},{"key":"2023020210383172000_B20","doi-asserted-by":"crossref","first-page":"2363","DOI":"10.1101\/gr.1680803","article-title":"Development of human protein reference database as an initial platform for approaching systems biology in humans","volume":"13","author":"Peri","year":"2003","journal-title":"Genome Res."},{"key":"2023020210383172000_B21","doi-asserted-by":"crossref","first-page":"1236","DOI":"10.1093\/bioinformatics\/btg148","article-title":"Estimating the occurrence of false positives and false negatives in microarray studies by approximating and partitioning the empirical distribution of p-values","volume":"19","author":"Pounds","year":"2003","journal-title":"Bioinformatics"},{"key":"2023020210383172000_B22","volume-title":"R: A Language and Environment for Statistical Computing","author":"R Development Core Team","year":"2006"},{"key":"2023020210383172000_B23","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1093\/bioinformatics\/bti069","article-title":"Inferring pathways from gene lists using a literature-derived network of biological relationships","volume":"21","author":"Rajagopalan","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020210383172000_B24","doi-asserted-by":"crossref","first-page":"1937","DOI":"10.1056\/NEJMoa012914","article-title":"The use of molecular profiling to predict survival after chemotherapy for diffuse large-B-cell lymphoma","volume":"346","author":"Rosenwald","year":"2002","journal-title":"N. Engl. J. Med."},{"key":"2023020210383172000_B25","doi-asserted-by":"crossref","first-page":"2498","DOI":"10.1101\/gr.1239303","article-title":"Cytoscape: a software environment for integrated models of biomolecular interaction networks","volume":"13","author":"Shannon","year":"2003","journal-title":"Genome Res."},{"key":"2023020210383172000_B26","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1038\/nbt1196","article-title":"Modeling cellular machinery through biological network comparison","volume":"24","author":"Sharan","year":"2006","journal-title":"Nat. Biotechno."},{"key":"2023020210383172000_B27","doi-asserted-by":"crossref","first-page":"3940","DOI":"10.1093\/bioinformatics\/bti623","article-title":"ROCR: visualizing classifier performance in R","volume":"21","author":"Sing","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020210383172000_B28","doi-asserted-by":"crossref","DOI":"10.2202\/1544-6115.1027","article-title":"Linear models and empirical Bayes methods for assessing differential expression in microarray experiments","volume":"3","author":"Smyth","year":"2004","journal-title":"Stat. Appl. Genet. Mol. Biol"},{"key":"2023020210383172000_B29","doi-asserted-by":"crossref","first-page":"1517","DOI":"10.1093\/bioinformatics\/bth112","article-title":"New methods for joint analysis of biological networks and expression data","volume":"20","author":"Sohler","year":"2004","journal-title":"Bioinformatics"},{"key":"2023020210383172000_B30","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1093\/bib\/bbm038","article-title":"Current progress in network research: toward reference networks for key model organisms","volume":"8","author":"Srinivasan","year":"2007","journal-title":"Brief Bioinform."},{"key":"2023020210383172000_B31","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1093\/biomet\/77.1.147","article-title":"Martingale-based residuals for survival models","volume":"77","author":"Therneau","year":"1990","journal-title":"Biometrika"},{"issue":"Database issue","key":"2023020210383172000_B32","doi-asserted-by":"crossref","first-page":"D358","DOI":"10.1093\/nar\/gkl825","article-title":"STRING 7\u2013recent developments in the integration and prediction of protein interactions","volume":"35","author":"von Mering","year":"2007","journal-title":"Nucleic Acids Res"},{"key":"2023020210383172000_B33","volume-title":"All of Statistics: A concise course in statistical inference","author":"Wasserman","year":"2005","edition":"2nd edn"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i223\/49054194\/bioinformatics_24_13_i223.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i223\/49054194\/bioinformatics_24_13_i223.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T12:20:27Z","timestamp":1675340427000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/13\/i223\/231653"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,1]]},"references-count":33,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2008,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn161","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,7,1]]},"published":{"date-parts":[[2008,7,1]]}}}