Bioinformatics Advance Access originally published online on December 21, 2004
Bioinformatics 2005 21(8):1739-1740; doi:10.1093/bioinformatics/bti228
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
expa: a program for calculating extreme pathways in biochemical reaction networks
Department of Bioengineering, University of California San Diego, La Jolla, CA 92093, USA
*To whom correspondence should be addressed.
 |
Abstract |
|---|
 TOP Abstract 1 INTRODUCTION2 DESCRIPTION OF THE...3 IMPLEMENTATION4 FEATURESREFERENCES |
|---|
Summary: The set of extreme pathways, a generating set for all possible steady-state flux maps in a biochemical reaction network, can be computed from the stoichiometric matrix, an incidence-like matrix reflecting the network topology. Here, we describe the implementation of a well-known algorithm to compute these pathways and give a summary of the features of the available software.
Availability: The C-code, along with a Windows executable and sample network reaction files, are available at http://systemsbiology.ucsd.edu
Contact: palsson{at}ucsd.edu
|
1 INTRODUCTION |
|---|
|
TOPAbstract1 INTRODUCTION2 DESCRIPTION OF THE...3 IMPLEMENTATION4 FEATURESREFERENCES |
|---|
The abundance of genomic data available today allows for construction of genome-scale metabolic networks for many organisms. The topology of the type of networks considered here is determined by an m x n stoichiometric matrix, S, whose rows and columns represent the system's metabolites and reactions, respectively. The dynamics of the system is given by
, where x is the m-dimensional vector of metabolite concentrations, ‘·’ denotes time-derivative, and v is a vector of fluxes which we assume is independent of concentrations and time.
Under the assumption that the system is in steady-state, we have that Sv = 0, and to obtain biologically feasible solutions to this equation, we also impose the condition that v 
0 (reversible reactions are split into two irreversible reactions—one for each direction). The set of solutions satisfying these constraints is a so-called convex cone which can be generated by a finite (and unique up to a multiple) number of vectors, i.e. each biologically feasible flux vector (when the system is in steady-state) can be expressed as a non-negative linear combination of these extreme pathways (Schilling et al., 2000). The extreme pathways are the edges of the convex cone, or more precisely, they are conically independent, i.e. no such vector can be expressed as a non-negative linear combination of any other vectors in the cone. The properties and uses of extreme pathways have been recently reviewed (Papin et al., 2003).
|
2 DESCRIPTION OF THE ALGORITHM |
|---|
|
TOPAbstract1 INTRODUCTION2 DESCRIPTION OF THE...3 IMPLEMENTATION4 FEATURESREFERENCES |
|---|
Given a metabolic network, where the metabolites are represented by the nodes and the edges represent the associated reactions, we compute the extreme pathways using an algorithm presented in Schilling et al. (2000) (see also Klamt, et al., 2003).
For the sake of brevity, we give here a simplified version of the extreme pathway algorithm. The algorithm may be described by a sequence of tableaux T0, T1,..., Tm, where the initial tableau is given by T0 = [I S'], and the final tableau Tm = [P 0]. Here, I is the n x n identity matrix, ‘prime’ denotes transpose, P is a matrix with n columns whose rows are the extreme pathways and 0 is a matrix with m columns and all entries equal to zero (determining the number of rows in the final tableau is an open problem). Converting the right hand matrix S' to the zero matrix is done column by column using elementary row operations, each tableaux corresponding to a column, as follows. For each 1 
i m, the tableau Ti is obtained from Ti–1 by first choosing a column of the right-hand matrix (originating from S') to zero out, say column j. Suppose there are pos positive, neg negative and z zero elements in column j. First, the z rows of Ti–1 containing a zero in column j are copied to Ti. Then each of the pos rows is combined (using an elementary row operation) with each of the neg rows to produce a zero in column j of Ti. More precisely, if 
and 
for some s and t, then 
is the new row to be added to Ti. (Here, 
denotes the sth row, 
is the (s,j)-element in the tableau Ti–1 and |x| is the absolute value of x.) Finally, only rows which are conically independent are retained in Ti : for any two rows x, y, if A(x) 
A(y), then row x is deleted from the tableau, where A(x) = {i : xi = 0}, the indices of the zero components of x. Hence, the number of rows in Ti is at most z + neg * pos.
|
3 IMPLEMENTATION |
|---|
|
TOPAbstract1 INTRODUCTION2 DESCRIPTION OF THE...3 IMPLEMENTATION4 FEATURESREFERENCES |
|---|
The tableaux are implemented as matrices (two-dimensional arrays) using pointers to pointers as described in Appendix B of Press et al. (1992). This means that the rows of the matrices are not necessarily stored in contiguous locations in memory (since rows are added and deleted with each iteration, it would be inefficient to store the matrices in continuous chunks of memory). For each iteration i = 1, 2, ..., m, two matrices are used, one containing the tableau from the previous iteration, Ti–1, and the other for constructing the next tableau, Ti. These matrices are in sparse form, i.e. only the non-zero elements are stored in memory. The column indices corresponding to the non-zero elements in each row of the matrices are accounted for by bit map representations of the matrices [similiar to the ones used by Samatova et al. (2002)]. These bitmaps are also implemented as matrices of the type described above, but here each row consists of w words, where w =
(m + n)/sizeof(word)
, i.e. each row is represented by a pointer which points to a location in memory of size w words.
For the following, assume (for simplicity) that the expression inside the ceiling operator of the definition of w is an integer. The conical independence check is done with AND logical bit operations using bit representations of the rows (if x and y are bit rows and, ((
x[i]) and y[i]) is non-zero, for some 0 i w – 1 then A(x) 
A(y), where denotes bit negation). Each of the candidate pos * neg rows (if 
and 
are rows of opposite signs, then a new row, 
, is constructed by doing = | , where | denotes bitwise AND and the operation is performed word by word) is checked against the existing rows of the next bit matrix, and based on the outcome of the test, its bit representation is added to the bit array and a corresponding sparse row is added to the next sparse matrix (at the start of the iteration the next matrix consists of the z zero rows determined by the current column). The pivoting column chosen in each iteration is one whose quantity pos * neg is a minimum (of the columns not yet processed). This choice minimizes the amount of work done when constructing the next tableau and may be thought of as a local (or greedy) optimization strategy (an interesting open problem is how to choose columns based on some global optimization criterion). The conical independence check described above is by far the most computationally intensive part of the algorithm. To decrease the number of checks necessary, it may be possible to partition the rows into equivalence classes based on the zero index sets A(·) so that only a subset of the neg * pos rows need be checked for a particular candidate row (Samatova et al., 2002). This feature has not yet been implemented in our program.
Other implementations include (see Klamt et al., 2003; Samatova et al., 2002).
|
4 FEATURES |
|---|
|
TOPAbstract1 INTRODUCTION2 DESCRIPTION OF THE...3 IMPLEMENTATION4 FEATURESREFERENCES |
|---|
The open-source software comes with a command line interface, where the user is provided with input options and help menu by typing expa with no arguments or expa -h, respectively. To calculate the extreme pathways, the user has the option of specifying the network topology in the form of the stoichiometric matrix or the corresponding metabolic reactions.
The matrix file is an ASCII file where each row of the matrix constitutes a line (ended by a new line character) and each matrix entry is separated by white space. In addition, the user must supply the dimensions of the matrix, and the number and types of the so-called exchange fluxes (see Schilling et al., 2000). Being able to use the stoichimetric matrix as input is useful if preprocessing of the matrix is desired (e.g. permuting or removing columns).
The reaction file is also an ASCII file and contains all the reactions in the metabolic network, one on each line of the file. The exact form of the entries is described in the README file on our website, and several sample files are provided there as well.
The extreme pathways are output to a file named ‘Paths.txt’ in matrix form, where each row is a pathway.
|
Acknowledgments |
|---|
Financial support for this work was provided by a grant from the National Institutes of Health (GM68837). Bernhard Palsson serves on the Scientific Advisory board of Genomatica.
Received on September 10, 2004; revised on October 20, 2004; accepted on December 13, 2004
|
REFERENCES |
|---|
|
TOPAbstract1 INTRODUCTION2 DESCRIPTION OF THE...3 IMPLEMENTATION4 FEATURESREFERENCES |
|---|
Klamt, S., Stelling, J., Ginkel, M., Dieter, G. (2003) FluxAnalyzer: exploring structure, pathways, and flux distributions in metabolic networks on interactive flux maps. Bioinformatics, 19, 261–269
Papin, J.A., Price, N.D., Wiback, S.J., Fell, D.A., Palsson, B.Ø. (2003) Metabolic pathways in the post-genome era. Trends Biochem. Sci., 28, 250–258[CrossRef][Web of Science][Medline].
Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P. Numerical Recipes in C, The Art of Scientific Computing, (1992) 2nd edn. Cambridge University Press.
Samatova, F.N., Geist, A., Ostrouchov, G., Melechko, A. (2002) Parallel out-of-core algorithm for genome-scale enumeration of metabolic systemic pathways. Proceedings of the First IEEE Workshop on High Performance Computational Biolology (HICOMB2002), , Ft. Lauderdale, FL (http://www.hicomb.org/hicomb2003/papers/HICOMB2-6.pdf).
Schilling, C.H., Letscher, D., Palsson, B.Ø. (2000) Theory for the systemic definition of metabolic pathways and their use in interpreting metabolic function from a pathway-oriented perspective. J. Theoret. Biol., 203, 249–283[CrossRef][Web of Science][Medline].
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  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]
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||