Metabolic PathFinding: inferring relevant pathways in biochemical networks.Croes D, Couche F, Wodak SJ, van Helden J.
SCMBB, Universite Libre de Bruxelles, Campus Plaine, CP 263, Boulevard du Triomphe, B-1050 Bruxelles, Belgium.
Our knowledge of metabolism can be represented as a network comprising several thousands of nodes (compounds and reactions). Several groups applied graph theory to analyse the topological properties of this network and to infer metabolic pathways by path finding. This is, however, not straightforward, with a major problem caused by traversing irrelevant shortcuts through highly connected nodes, which correspond to pool metabolites and co-factors (e.g. H2O, NADP and H+). In this study, we present a web server implementing two simple approaches, which circumvent this problem, thereby improving the relevance of the inferred pathways. In the simplest approach, the shortest path is computed, while filtering out the selection of highly connected compounds. In the second approach, the shortest path is computed on the weighted metabolic graph where each compound is assigned a weight equal to its connectivity in the network. This approach significantly increases the accuracy of the inferred pathways, enabling the correct inference of relatively long pathways (e.g. with as many as eight intermediate reactions). Available options include the calculation of the k-shortest paths between two specified seed nodes (either compounds or reactions). Multiple requests can be submitted in a queue. Results are returned by email, in textual as well as graphical formats (available in http://www.scmbb.ulb.ac.be/pathfinding/).
Nucleic Acids Res. 2005 Jul 1;33(Web Server issue):W326-30.
Article IN PRESS by the Journal of Molecular Biology:
Inferring Meaningful Pathways in Weighted Metabolic Networks
Didier Croesa, Fabian Couchea, Shoshana J. Wodaka, b and Jacques van Heldena,
aSCMBB-Université Libre de Bruxelles, Campus Plaine, CP 263, Boulevard du Triomphe, 1050 Bruxelles, Belgium
bStructural Biology and Biochemistry Program, Hospital for Sick Children, 555 University Avenue, Toronto, Ont. M5G 1X8, Canada
Received 16 January 2005; revised 6 September 2005; accepted 27 September 2005. Edited by J. Thornton. Available online 17 October 2005.
An approach is presented for computing meaningful pathways in the network of small molecule metabolism comprising the chemical reactions characterized in all organisms. The metabolic network is described as a weighted graph in which all the compounds are included, but each compound is assigned a weight equal to the number of reactions in which it participates. Path finding is performed in this graph by searching for one or more paths with lowest weight. Performance is evaluated systematically by computing paths between the first and last reactions in annotated metabolic pathways, and comparing the intermediate reactions in the computed pathways to those in the annotated ones. For the sake of comparison, paths are computed also in the un-weighted raw (all compounds and reactions) and filtered (highly connected pool metabolites removed) metabolic graphs, respectively. The correspondence between the computed and annotated pathways is very poor (<30%) in the raw graph; increasing to 65% in the filtered graph; reaching 85% in the weighted graph. Considering the best-matching path among the five lightest paths increases the correspondence to 92%, on average. We then show that the average distance between pairs of metabolites is significantly larger in the weighted graph than in the raw unfiltered graph, suggesting that the small-world properties previously reported for metabolic networks probably result from irrelevant shortcuts through pool metabolites. In addition, we provide evidence that the length of the shortest path in the weighted graph represents a valid measure of the “metabolic distance” between enzymes.
We suggest that the success of our simplistic approach is rooted in the high degree of specificity of the reactions in metabolic pathways, presumably reflecting thermodynamic constraints operating in these pathways. We expect our approach to find useful applications in inferring metabolic pathways in newly sequenced genomes.
Keywords: path finding; weighted graph; metabolic network; metabolic pathways; pathway inference
Abbreviations used: SMM, small molecules metabolism; PPV, positive predictive value; KEGG, Kyoto Encyclopedia of Genes and Genomes
Fell DA, Wagner A. The small world of metabolism. Nat Biotechnol. 2000 Nov;18(11):1121-2.
Jeong H, Tombor B, Albert R, Oltvai ZN, Barabasi AL. The large-scale organization of metabolic networks. Nature. 2000 Oct 5;407(6804):651-4.
Ravasz E, Somera AL, Mongru DA, Oltvai ZN, Barabasi AL. Hierarchical organization of modularity in metabolic networks. Science. 2002 Aug 30;297(5586):1551-5.
Rison SC, Teichmann SA, Thornton JM. Homology, pathway distance and chromosomal localization of the small molecule metabolism enzymes in Escherichia coli. J Mol Biol. 2002 May 3;318(3):911-32.
Simeonidis E, Rison SC, Thornton JM, Bogle ID, Papageorgiou LG. Analysis of metabolic networks using a pathway distance metric through linear programming. Metab Eng. 2003 Jul;5(3):211-9.
van Helden J, Wernisch L, Gilbert D, Wodak SJ. Graph-based analysis of metabolic networks. Ernst Schering Res Found Workshop. 2002;(38):245-74.
Wagner A, Fell DA. The small world inside large metabolic networks. Proc R Soc Lond B Biol Sci. 2001 Sep 7;268(1478):1803-10.
Lemer C, Antezana E, Couche F, Fays F, Santolaria X, Janky R, Deville Y, Richelle J, Wodak SJ. The aMAZE LightBench: a web interface to a relational database of cellular processes. Nucleic Acids Res. 2004 Jan 1;32 Database issue:D443-8.
van Helden J, Naim A, Lemer C, Mancuso R, Eldridge M, Wodak SJ. From molecular activities and processes to biological function. Brief Bioinform. 2001 Mar;2(1):81-93.
van Helden J, Naim A, Mancuso R, Eldridge M, Wernisch L, Gilbert D, Wodak SJ. Representing and analysing molecular and cellular function using the computer. Biol Chem. 2000 Sep-Oct;381(9-10):921-35.