Abstract
Pathway analysis is a powerful tool to study metabolic reaction networks under steady state conditions. An Elementary pathway constitutes a minimal set of reactions that can operate at steady state such that each reaction also proceeds in the appropriate direction. In mathematical terms, elementary pathways are the extreme rays of a polyhedral cone—the solution set of homogeneous equality and inequality constraints. Enumerating all extreme rays—given the constraints—is difficult especially if the problem is degenerate and high dimensional. We present and compare two approaches for the parallel enumeration of extreme rays, both based on the double description method. This iterative algorithm has proven efficient especially for degenerate problems, but is difficult to parallelize due to its sequential operation. The first approach parallelizes single iteration steps individually. In the second approach, we introduce a born/die matrix to store intermediary results, allowing for parallelization across several iteration steps. We test our multi-core implementations on a 16 core machine using large examples from combinatorics and biology.
Availability: The implementation is available at http://csb.ethz.ch in the tools section (Java binaries); sources are available from the authors upon request.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Schuster, S., Hilgetag, C.: On elementary flux modes in biochemical reaction systems at steady state. J. Biol. Syst. 2, 165–182 (1994)
Stelling, J., Klamt, S., Bettenbrock, K., Schuster, S., Gilles, E.: Metabolic network structure determines key aspects of functionality and regulation. Nature 420, 190–193 (2002)
Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1-3), 21–46 (1996)
Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V.: Generating all vertices of a polyhedron is hard. Discrete Comput. Geom. 39(1), 174–190 (2008)
Motzkin, T.S., Raiffa, H., Thompson, G., Thrall, R.M.: The double description method. In: Kuhn, H., Tucker, A. (eds.) Contributions to the Theory of Games II. Annals of Math. Studies, vol. 8, pp. 51–73. Princeton University Press, Princeton (1953)
Wagner, C.: Nullspace approach to determine the elementary modes of chemical reaction systems. J. Phys. Chem. B 108, 2425–2431 (2004)
Gagneur, J., Klamt, S.: Computation of elementary modes: A unifying framework and the new binary approach. BMC Bioinformatics 5, 175 (2004)
Terzer, M., Stelling, J.: Large scale computation of elementary flux modes with bit pattern trees. Bioinformatics 24(19), 2229–2235 (2008)
Fukuda, K., Prodon, A.: Double description method revisited. In: Combinatorics and Computer Science, pp. 91–111 (1995)
Fukuda, K.: cddlib-094, C–library for polyhedral computations, http://www.ifor.math.ethz.ch/~fukuda/cdd_home/index.html
4ti2 team: 4ti2—a software package for algebraic, geometric and combinatorial problems on linear spaces, www.4ti2.de
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Terzer, M., Stelling, J. (2010). Parallel Extreme Ray and Pathway Computation. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Wasniewski, J. (eds) Parallel Processing and Applied Mathematics. PPAM 2009. Lecture Notes in Computer Science, vol 6068. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14403-5_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-14403-5_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14402-8
Online ISBN: 978-3-642-14403-5
eBook Packages: Computer ScienceComputer Science (R0)