Bioinformatics Advance Access originally published online on May 26, 2006
Bioinformatics 2006 22(15):1930-1931; doi:10.1093/bioinformatics/btl267
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Metatool 5.0: fast and flexible elementary modes analysis
Department of Bioinformatics, Friedrich-Schiller-University Jena 07743 Jena, Germany
*To whom correspondence should be addressed.
 |
ABSTRACT |
|---|
 TOP ABSTRACT REFERENCES |
|---|
Summary: Elementary modes analysis is a powerful tool in the constraint-based modeling of metabolic networks. In recent years, new approaches to calculating elementary modes in biochemical reaction networks have been developed. As a consequence, the program Metatool, which is one of the first programs dedicated to this purpose, has been reimplemented in order to make use of these new approaches. The performance of Metatool has been significantly increased and the new version 5.0 can now be run inside the GNU octave or Matlab environments to allow more flexible usage and integration with other tools.
Availability: The script files and compiled shared libraries can be downloaded from the Metatool website at http://pinguin.biologie.uni-jena.de/bioinformatik/networks/index.html. Metatool consists of script files (m-files) for GNU octave as well as Matlab and shared libraries. The scripts are licensed under the GNU Public License and the use of the shared libraries is free for academic users and testing purposes. Commercial use of Metatool requires a special contract.
Contact: kamp{at}minet.uni-jena.de
Elementary modes analysis has become an important method for the study of metabolic networks (Schuster et al., 2000, 2002). It allows one to systematically enumerate all independent minimal pathways through a network that are stoichiometrically and thermodynamically feasible. This has been applied to various biochemical systems in view of medical and biotechnological applications (Schwender et al., 2004; Carlson and Srienc, 2004; Papin et al., 2004). As inputs, the reaction stoichiometries and reversibilities have to be known. In addition, the metabolites have to be classified as either external or internal. External metabolites are assumed to be buffered while internal metabolites have to be balanced by production and consumption reactions in the network. The stoichiometric coefficients are collected into a matrix N, where rows correspond to internal metabolites and columns to reactions. Note that the reaction reversibilities are not integrated into the matrix N, but are taken into account later.
Elementary modes are flux distributions of the metabolic network in steady state (expressed by the equation N·v = 0) with the fluxes through irreversible reactions going in the appropriate direction. In addition, elementary modes have to be independent of each other, which means that the reactions of any elementary mode must not be a subset of the reactions of any other mode.
In the previous versions of Metatool, the algorithm described in Schuster et al. (2000) was used to calculate the elementary modes. In contrast, the current version is based on the algorithm proposed by Urbanczik and Wagner (2005), which empirically shows a higher performance. Both algorithms can be seen as variants of the double-description method for enumerating all extreme rays of a polyhedral cone (Gagneur and Klamt, 2004). Moreover, they are similar to methods proposed in the theory of Petri nets (Colom and Silva, 1991). The current implementation (version 5.0) differs from the description by Urbanczik and Wagner (2005) in that the test of candidate modes for their mutual independence is now performed by an algebraic test.
The previous versions of Metatool were stand-alone programs compiled from C/C++ source code with simple text input and output. This has the drawback that it is difficult for the user to make changes to the calculation procedure because this would require advanced programming knowledge. Another drawback results from the cumbersome exchange of input and output via text files with other programs, for instance for post-processing the results. Therefore, Metatool is now embedded in the math environments GNU octave and Matlab. It consists of script files that are compatible with both programs and shared libraries that are specifically compiled for each program and operating system. To understand and modify these scripts only basic programming knowledge is required. The shared libraries are built from C++ sources that have been completely rewritten for this purpose.
As input, Metatool can still read the standard input files used by the previous versions. Additionally, a stoichiometric matrix and a vector that specifies reaction reversibilities can be directly used as inputs. Because Metatool is now embedded in a math environment, the results are returned as a data structure which can be processed with the standard commands of these environments. Furthermore, the results can be analyzed by custom scripts. Thus it is, for example, easily possible to calculate the yields of the elementary modes with respect to specified substrate/product pairs. The usage of Metatool and the format of the input/output data structures are described in more detail on the Metatool web pages.
With the help of the Matlab compiler, a stand-alone version of Metatool can be created. Such a program will require some additional Matlab libraries that can be distributed freely so that it is not necessary to have a Matlab installation in order to use it. By default, this program reads a standard Metatool input file and produces an output file in a format similar to the previous versions. Optionally, the parser of Metatool can be used separately. One of the previous versions of Metatool has been embedded in the Systems Biology Workbench (Sauro et al., 2003). The new SBW–Matlab interface (Wellock et al., 2005) opens up the possibility to easily integrate the current version of Metatool into the SBW.
The central routines can now optionally be used by the FluxAnalyzer/CellNetAnalyzer (Klamt et al., 2003), which thereby profits from the increased performance of Metatool.
The previous versions of Metatool came in two variants, one for integer and one for floating-point calculations. The current version internally distinguishes stoichiometric matrices that only contain integers from those that also contain floating-point numbers. When only integers are present in the input, the results will also be integers. In both cases, floating-point numbers with double precision are used to represent numbers because this is the default type of octave and Matlab. In the case of integer calculations, this allows for an exact representation of numbers up to ±(253 – 1). To prevent the explosion of integer coefficients through successive multiplications, the integer vectors are normalized by their greatest common divisor after each operation.
As mentioned above, Metatool 5.0 is based on the new algorithm proposed by Urbanczik and Wagner (2005). This has empirically been found to be faster for biochemical networks than the previously used algorithm presented in Schuster et al. (2000, 2002). One reason for the increased performance is the smaller initial tableau, because it contains the null-space of the stoichiometry matrix rather than the matrix itself. In addition, more vectors that are elementary already are carried over from the current tableau to the next one at each iteration step.
In contrast to the Urbanczik and Wagner (2005) algorithm, the test for mutual independence of elementary modes is made by checking the rank of a submatrix of the stoichiometry matrix. This algebraic test shows a significantly higher performance than the originally used combinatorial test (Klamt et al., 2005). The reason for this is that when using the combinatorial test each candidate mode has to be compared with all other modes. Therefore, this test scales, for each examined mode, with the number of preliminary modes, which is usually growing while the algorithm is running. The algebraic test on the other hand is independent of other modes and its worst-case time complexity is limited by parameters that are constant during run time.
To the best of our knowledge, Metatool is currently the fastest program for calculating elementary modes. The performance stems not only from algorithmic innovations but also from an efficient implementation in C++ that can be optimized well by modern compilers. The increase in speed and the reduction in memory requirements allows one to tackle larger reaction systems than before. For example, for a system of 112 reactions and 89 internal metabolites, describing the central metabolism in Escherichia coli, Metatool computes 2 450 787 elementary modes. This takes 87 min on a 2.4 GHz PC (Klamt et al., 2005). It was impossible to calculate such systems with earlier versions of Metatool.
Like earlier versions of Metatool, version 5.0 computes also other structural invariants besides elementary modes, such as conservation relations (cf. Heinrich and Schuster, 1996) and enzyme subsets (Pfeiffer et al., 1999) and fits a power law to the connectivity distribution of metabolites (Jeong et al., 2000).
The current reimplementation of Metatool basically produces the same output as the previous versions, but it is now possible to adapt the script files to one's needs with only basic programming skills. The enormous reduction in running time allows one to tackle larger reaction systems than before. This is of interest in view of the current efforts in analyzing genome-scale and whole-cell models.
Current developments to make use of distributed computing as described in Klamt et al. (2005) have led to a preliminary but already usable implementation. The use of distributed computation will not only speed up the calculations by using several processors in parallel, but will also make it possible to calculate even larger systems because each subprocess requires less resources (especially memory) than the complete task. Because the scripts for distributed computing are still in development, they are at present not included in Metatool.
An interesting question for future studies is whether the algorithm developed by Urbanczik and Wagner (2005) is faster for all chemical reaction systems than that proposed by Schuster et al. (2000). The fact that biochemical systems have arisen from biological evolution might imply special properties [e.g. the property to be scale-free (Jeong et al., 2000)] that favor one algorithm over another.
|
Acknowledgments |
|---|
We would like to thank Mihail Pachkov for his contributions to the Metatool program as well as Steffen Klamt and Julien Gagneur for helpful comments.
Conflict of Interest: none declared.
|
FOOTNOTES |
|---|
Associate Editor: Charlie Hodgman
Received on January 15, 2006; revised on May 16, 2006; accepted on May 18, 2006
|
REFERENCES |
|---|
|
TOPABSTRACTREFERENCES |
|---|
Carlson, R. and Srienc, F. (2004) Fundamental Escherichia coli biochemical pathways for biomass and energy production: identification of reactions. Biotechnol. Bioeng, . 85, 1–19[CrossRef][Web of Science][Medline].
Colom, J.M. and Silva, M. (1991) Convex geometry and semiflows in P/T nets. A comparative study of algorithms for computation of minimal P-semiflows. In Rozenberg, G. (Ed.). Advances In Petri Nets 1990, , Berlin Springer-Verlag, pp. 79–112.
Gagneur, J. and Klamt, S. (2004) Computation of elementary modes: a unifying framework and the new binary approach. BMC Bioinformatics, 5, 175–175[CrossRef][Medline].
Heinrich, R. and Schuster, S. The Regulation of Cellular Systems, Chapman and Hall, . (1996) , NY.
Jeong, H., et al. (2000) The large-scale organization of metabolic networks. Nature, 407, 651–654[CrossRef][Medline].
Klamt, S., et al. (2003) FluxAnalyzer: exploring structure, pathways, and flux distributions in metabolic networks on interactive flux maps. Bioinformatics, 19, 261–269
Klamt, S., et al. (2005) Algorithmic approaches for computing elementary modes in large biochemical reaction networks. IEE Proc. Syst. Biol, . 152, 249–255[CrossRef].
Papin, J.A., et al. (2004) Comparison of network-based pathway analysis methods. Trends Biotechnol, . 22, 400–405[CrossRef][Web of Science][Medline].
Pfeiffer, T., et al. (1999) METATOOL: for studying metabolic networks. Bioinformatics, 15, 251–257
Sauro, H.M., et al. (2003) Next generation simulation tools: the Systems Biology Workbench and BioSPICE integration. OMICS, 4, 355–372.
Schuster, S., et al. (2000) A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic networks. Nat. Biotechnol, . 18, 326–332[CrossRef][Web of Science][Medline].
Schuster, S., et al. (2002) Reaction routes in biochemical reaction systems: algebraic properties, validated calculation procedure and example from nucleotide metabolism. J. Math. Biol, . 45, 153–181[CrossRef][Web of Science][Medline].
Schwender, J., et al. (2004) Rubisco without the Calvin cycle improves the carbon efficiency of developing green seeds. Nature, 432, 779–782[CrossRef][Medline].
Urbanczik, R. and Wagner, C. (2005) An improved algorithm for stoichiometric network analysis: theory and applications. Bioinformatics, 21, 1203–1210
Wellock, C., et al. (2005) The SBW–MATLAB interface. Bioinformatics, 21, 823–824
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  K. Faust, D. Croes, and J. van Helden In response to 'Can sugars be produced from fatty acids? A test case for pathway analysis tools' Bioinformatics, December 1, 2009; 25(23): 3202 - 3205. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. F. de Figueiredo, A. Podhorski, A. Rubio, C. Kaleta, J. E. Beasley, S. Schuster, and F. J. Planes Computing the shortest elementary flux modes in genome-scale metabolic networks Bioinformatics, December 1, 2009; 25(23): 3158 - 3165. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. T. Trinh and F. Srienc Metabolic Engineering of Escherichia coli for Efficient Conversion of Glycerol to Ethanol Appl. Envir. Microbiol., November 1, 2009; 75(21): 6696 - 6705. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Kaleta, L. F. de Figueiredo, and S. Schuster Can the whole be less than the sum of its parts? Pathway analysis in genome-scale metabolic networks using elementary flux patterns Genome Res., October 1, 2009; 19(10): 1872 - 1883. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. F. de Figueiredo, S. Schuster, C. Kaleta, and D. A. Fell Can sugars be produced from fatty acids? A test case for pathway analysis tools Bioinformatics, January 1, 2009; 25(1): 152 - 158. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. F. de Figueiredo, S. Schuster, C. Kaleta, and D. A. Fell Can sugars be produced from fatty acids? A test case for pathway analysis tools Bioinformatics, November 15, 2008; 24(22): 2615 - 2621. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Blum and O. Kohlbacher MetaRoute: fast search for relevant metabolic routes for interactive network navigation and visualization Bioinformatics, September 15, 2008; 24(18): 2108 - 2109. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 F. J. Planes and J. E. Beasley A critical examination of stoichiometric and path-finding approaches to metabolic pathways Brief Bioinform, September 1, 2008; 9(5): 422 - 436. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. T. Trinh, P. Unrean, and F. Srienc Minimal Escherichia coli Cell for the Most Efficient Production of Ethanol from Hexoses and Pentoses Appl. Envir. Microbiol., June 15, 2008; 74(12): 3634 - 3643. [Abstract] [Full Text] [PDF]
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||