{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:11:05Z","timestamp":1768108265583,"version":"3.49.0"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2396,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,5,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Subgraph extraction is a powerful technique to predict pathways from biological networks and a set of query items (e.g. genes, proteins, compounds, etc.). It can be applied to a variety of different data types, such as gene expression, protein levels, operons or phylogenetic profiles. In this article, we investigate different approaches to extract relevant pathways from metabolic networks. Although these approaches have been adapted to metabolic networks, they are generic enough to be adjusted to other biological networks as well.<\/jats:p>\n               <jats:p>Results: We comparatively evaluated seven sub-network extraction approaches on 71 known metabolic pathways from Saccharomyces cerevisiae and a metabolic network obtained from MetaCyc. The best performing approach is a novel hybrid strategy, which combines a random walk-based reduction of the graph with a shortest paths-based algorithm, and which recovers the reference pathways with an accuracy of \u223c77%.<\/jats:p>\n               <jats:p>Availability: Most of the presented algorithms are available as part of the network analysis tool set (NeAT). The kWalks method is released under the GPL3 license.<\/jats:p>\n               <jats:p>Contact: \u00a0kfaust@ulb.ac.be<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq105","type":"journal-article","created":{"date-parts":[[2010,3,13]],"date-time":"2010-03-13T01:26:00Z","timestamp":1268443560000},"page":"1211-1218","source":"Crossref","is-referenced-by-count":74,"title":["Pathway discovery in metabolic networks by subgraph extraction"],"prefix":"10.1093","volume":"26","author":[{"given":"Karoline","family":"Faust","sequence":"first","affiliation":[{"name":"1 Laboratoire de Bioinformatique des G\u00e9nomes et des R\u00e9seaux (BiGRe), Universit\u00e9 Libre de Bruxelles, Campus Plaine\u2014CP263, Boulevard du Triomphe, 1050 Bruxelles and 2 UCL Machine Learning Group, Computing Science and Engineering Department, Universit\u00e9 catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium"}]},{"given":"Pierre","family":"Dupont","sequence":"additional","affiliation":[{"name":"1 Laboratoire de Bioinformatique des G\u00e9nomes et des R\u00e9seaux (BiGRe), Universit\u00e9 Libre de Bruxelles, Campus Plaine\u2014CP263, Boulevard du Triomphe, 1050 Bruxelles and 2 UCL Machine Learning Group, Computing Science and Engineering Department, Universit\u00e9 catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium"}]},{"given":"J\u00e9r\u00f4me","family":"Callut","sequence":"additional","affiliation":[{"name":"1 Laboratoire de Bioinformatique des G\u00e9nomes et des R\u00e9seaux (BiGRe), Universit\u00e9 Libre de Bruxelles, Campus Plaine\u2014CP263, Boulevard du Triomphe, 1050 Bruxelles and 2 UCL Machine Learning Group, Computing Science and Engineering Department, Universit\u00e9 catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium"}]},{"given":"Jacques","family":"van Helden","sequence":"additional","affiliation":[{"name":"1 Laboratoire de Bioinformatique des G\u00e9nomes et des R\u00e9seaux (BiGRe), Universit\u00e9 Libre de Bruxelles, Campus Plaine\u2014CP263, Boulevard du Triomphe, 1050 Bruxelles and 2 UCL Machine Learning Group, Computing Science and Engineering Department, Universit\u00e9 catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium"}]}],"member":"286","published-online":{"date-parts":[[2010,3,12]]},"reference":[{"key":"2023012508154730500_B1","doi-asserted-by":"crossref","DOI":"10.1186\/gb-2008-9-12-r179","article-title":"KEGG spider: interpretation of genomics data in the context of the global gene metabolic network","volume":"9","author":"Antonov","year":"2008","journal-title":"Genome Biol."},{"key":"2023012508154730500_B2","doi-asserted-by":"crossref","first-page":"2084","DOI":"10.1111\/j.1742-4658.2009.06943.x","article-title":"TICL - a web tool for network-based interpretation of compound lists inferred by high-throughput metabolomics","volume":"276","author":"Antonov","year":"2009","journal-title":"FEBS J."},{"key":"2023012508154730500_B3","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0928-4869(00)00006-9","article-title":"Metabolic reconstruction using shortest paths","volume":"8","author":"Arita","year":"2000","journal-title":"Simul. Pract. Theory"},{"key":"2023012508154730500_B4","article-title":"Steiner tree problems in the analysis of biological networks","volume-title":"Master's Thesis","author":"Betzler","year":"2005"},{"key":"2023012508154730500_B5","doi-asserted-by":"crossref","first-page":"2108","DOI":"10.1093\/bioinformatics\/btn360","article-title":"MetaRoute: fast search for relevant metabolic routes for interactive network navigation and visualization","volume":"24","author":"Blum","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012508154730500_B6","doi-asserted-by":"crossref","first-page":"W444","DOI":"10.1093\/nar\/gkn336","article-title":"NeAT: a toolbox for the analysis of biological networks, clusters, classes and pathways","volume":"36","author":"Broh\u00e9e","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012508154730500_B7","article-title":"First passage times dynamics in Markov models with applications to HMM induction, sequence classification, and graph mining","volume-title":"PhD Thesis","author":"Callut","year":"2007"},{"key":"2023012508154730500_B8","doi-asserted-by":"crossref","first-page":"D623","DOI":"10.1093\/nar\/gkm900","article-title":"The MetaCyc database of metabolic pathways and enzymes and the BioCyc collection of Pathway\/Genome databases","volume":"36","author":"Caspi","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023012508154730500_B9","doi-asserted-by":"crossref","first-page":"W326","DOI":"10.1093\/nar\/gki437","article-title":"Metabolic PathFinding: inferring relevant pathways in biochemical networks","volume":"33","author":"Croes","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012508154730500_B10","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.jmb.2005.09.079","article-title":"Inferring meaningful pathways in weighted metabolic networks","volume":"356","author":"Croes","year":"2006","journal-title":"J. Mol. Biol."},{"key":"2023012508154730500_B11","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numerische Mathematik"},{"key":"2023012508154730500_B12","doi-asserted-by":"crossref","first-page":"i223","DOI":"10.1093\/bioinformatics\/btn161","article-title":"Identifying functional modules in protein-protein interaction networks: an integrated exact approach","volume":"24","author":"Dittrich","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012508154730500_B13","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0377-2217(02)00707-5","article-title":"Solving group Steiner problems as Steiner problems","volume":"154","author":"Duin","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"2023012508154730500_B14","article-title":"Relevant subgraph extraction from random walks in a graph","volume-title":"Research Report UCL\/FSA\/INGI RR 2006-07","author":"Dupont","year":"2006"},{"key":"2023012508154730500_B15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-1-1","article-title":"Metabolic flux balance analysis and the in silico analysis of Escherichia coli k-12 gene deletions","volume":"1","author":"Edwards","year":"2000","journal-title":"BMC Bioinformatics"},{"key":"2023012508154730500_B16","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/j.jmb.2009.03.006","article-title":"Metabolic path finding using RPAIR annotation","volume":"388","author":"Faust","year":"2009","journal-title":"J. Mol. Biol."},{"key":"2023012508154730500_B17","article-title":"The Steiner tree problem","volume-title":"Annals of Discrete Mathematics","author":"Hwang","year":"1992"},{"key":"2023012508154730500_B18","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":"2023012508154730500_B19","first-page":"15","article-title":"Computing the k shortest paths: a new algorithm and an experimental comparison","volume-title":"Proceedings of the Third International Workshop on Algorithm Engineering (WAE 1999)","author":"Jimenez","year":"1999"},{"key":"2023012508154730500_B20","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among combinatorial problems","volume-title":"Complexity of Computer Computations.","author":"Karp","year":"1972"},{"key":"2023012508154730500_B21","volume-title":"Finite Markov Chains.","author":"Kemeny","year":"1983"},{"key":"2023012508154730500_B22","doi-asserted-by":"crossref","first-page":"D464","DOI":"10.1093\/nar\/gkn751","article-title":"EcoCyc: a comprehensive view of Escherichia coli biology","volume":"37","author":"Keseler","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023012508154730500_B23","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1006\/jagm.1995.1029","article-title":"A nearly best-possible approximation algorithm for node-weighted Steiner trees","volume":"19","author":"Klein","year":"1995","journal-title":"J. Algorithms"},{"key":"2023012508154730500_B24","doi-asserted-by":"crossref","first-page":"D438","DOI":"10.1093\/nar\/gkh100","article-title":"MetaCyc: a multiorganism database of metabolic pathways and enzymes","volume":"32","author":"Krieger","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012508154730500_B25","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1093\/bib\/bbl007","article-title":"Flux balance analysis in the era of metabolomics","volume":"7","author":"Lee","year":"2006","journal-title":"Brief. Bioinformatics"},{"key":"2023012508154730500_B26","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1093\/bfgp\/eln011","article-title":"Automated extraction of meaningful pathways from quantitative proteomics data","volume":"7","author":"Noirel","year":"2008","journal-title":"Brief. Funct. Genomic. Proteomic."},{"key":"2023012508154730500_B27","doi-asserted-by":"crossref","first-page":"1189","DOI":"10.1093\/bioinformatics\/bti116","article-title":"Metabolic pathway analysis web service (Pathway Hunter Tool at CUBIC)","volume":"21","author":"Rahman","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012508154730500_B28","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":"2023012508154730500_B29","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0167-7799(98)01290-6","article-title":"Detection of elementary flux modes in biochemical networks: a promising tool for pathway analysis and metabolic engineering","volume":"17","author":"Schuster","year":"1999","journal-title":"TIBTECH"},{"key":"2023012508154730500_B30","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1074\/mcp.M400110-MCP200","article-title":"Identifying regulatory subnetworks for a set of genes","volume":"4","author":"Scott","year":"2005","journal-title":"Mol. Cell Proteomics"},{"key":"2023012508154730500_B31","first-page":"573","article-title":"An approximate solution for the Steiner problem in graphs","volume":"24","author":"Takahashi","year":"1980","journal-title":"Math. Jpn"},{"key":"2023012508154730500_B32","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1007\/s00253-008-1770-1","article-title":"Elementary mode analysis: a useful metabolic pathway analysis tool for characterizing cellular metabolism","volume":"81","author":"Trinh","year":"2009","journal-title":"Appl. Microbiol. Biotechnol."},{"key":"2023012508154730500_B33","first-page":"921","article-title":"Representing and analysing molecular and cellular function using the computer","volume":"381","author":"van Helden","year":"2000","journal-title":"Biol. Chem."},{"key":"2023012508154730500_B34","first-page":"245","article-title":"Graph-based analysis of metabolic networks","volume-title":"Ernst Schering Res Found Workshop","author":"van Helden","year":"2002"},{"key":"2023012508154730500_B35","first-page":"407","article-title":"Analysis of gene expression data with pathway scores","volume-title":"Proceedings of the International Conference of Intelligent Systems Molecular Biology","author":"Zien","year":"2000"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/9\/1211\/48854911\/bioinformatics_26_9_1211.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/9\/1211\/48854911\/bioinformatics_26_9_1211.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:16:30Z","timestamp":1674634590000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/9\/1211\/199334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,12]]},"references-count":35,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2010,5,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq105","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,5,1]]},"published":{"date-parts":[[2010,3,12]]}}}