Review Article  Open Access
Francisco Llaneras, Jesús Picó, "Which Metabolic Pathways Generate and Characterize the Flux Space? A Comparison among Elementary Modes, Extreme Pathways and Minimal Generators", BioMed Research International, vol. 2010, Article ID 753904, 13 pages, 2010. https://doi.org/10.1155/2010/753904
Which Metabolic Pathways Generate and Characterize the Flux Space? A Comparison among Elementary Modes, Extreme Pathways and Minimal Generators
Abstract
Important efforts are being done to systematically identify the relevant pathways in a metabolic network. Unsurprisingly, there is not a unique set of networkbased pathways to be tagged as relevant, and at least four related concepts have been proposed: extreme currents, elementary modes, extreme pathways, and minimal generators. Basically, there are two properties that these sets of pathways can hold: they can generate the flux space—if every feasible flux distribution can be represented as a nonnegative combination of flux through them—or they can comprise all the nondecomposable pathways in the network. The four concepts fulfill the first property, but only the elementary modes fulfill the second one. This subtle difference has been a source of errors and misunderstandings. This paper attempts to clarify the intricate relationship between the networkbased pathways performing a comparison among them.
1. Introduction
A metabolic network can be represented with a stoichiometric matrix N, where rows correspond to the m metabolites and columns to the reactions. Assuming that intracellular metabolites are at steady state, material balances can be formulated as follows [1]: where is the dimensional vector of flux through each reaction. Each feasible steady state is represented by a flux vector v. Taking into account these mass balances and the irreversibility of certain reactions, the space of feasible steady state flux distributions, or flux space, can be defined as follows (see glossary for words in italics): where D is a diagonal matrix with if the flux is irreversible (otherwise 0).
The concept of the flux space is the cornerstone of constraintbased modeling, an approach supported by the fact that cells are subject to governing constraints that limit their behavior [2, 3]. In this context, networkbased pathways are used to investigate the modeled metabolism by the analysis of a finite set of relevant pathways, which ideally represents all of the metabolic states that a cell can show. Some outstanding applications of this approach are enumerated in Table 1.

However, there is not a unique set of networkbased pathways to be tagged as “relevant” and different proposals have been applied with success: extreme currents, elementary modes, extreme pathways, and minimal generators. These concepts are not equivalent, but closely related. There are three major properties that a set of networkbased pathways can hold: (P1) they can generate the flux space P, (P2) they can be the minimal set of vectors fulfilling the first property, and (P3) they can be all the nondecomposable pathways in the network. The fact that all of the networkbased pathways—elementary modes, extreme pathways, and so forth—fulfill the first property but not the others has been a source of errors, imprecisión, and misunderstandings.
This paper discusses the relationship between the different networkbased pathways from a theoretical point of view. We will start defining four pathway concepts and then we will perform a comparison among them. Finally, we will present some examples and outline the major conclusions.
2. Results and Discussion
The first attempts to systemically extract a set of pathways from a given metabolic network were based on the assumption that all of the fluxes were irreversible, or more precisely, that its dominant direction could be presumed. Convex algebra shows that in this case the flux space P is a pointed convex polyhedral cone in the positive orthant , which can be generated by nonnegative combination of certain vectors, its edges, or extreme rays [32]. See Figure 1 for a geometric illustration of the concept.
(a)
(b)
These extreme rays were flux vectors, or pathways, with a remarkable property (P1): the extreme rays generate the flux space P; that is, every flux distribution v in P can be represented as a nonnegative combination of fluxes through these pathways ( denotes the extreme rays): Notice that, in general, a given v cannot be uniquely decomposed into an activity pattern w, but a space of valid solutions exists [22, 23]. This is also true for the rest of generating sets that will be introduced in subsequent sections.
Moreover, the set of extreme rays had two additional properties: (P2) it was the smallest (minimal) generating set of P, and (P3) the extreme rays were all the nondecomposable vectors in P, those that cannot be decomposed in simpler vectors [6]. A nondecomposable vector is a minimal set of reactions that form a “functional unit”; if any of its participant reactions is not carrying flux, the others cannot operate alone. These functional units are the simplest steadystate flux distributions that cells can show, and the rest of feasible states can be seen as the aggregated action of these units. This property makes it possible to investigate the infinite behaviors that cells can show by inspection of the finite set of nondecomposable vectors.
But what happens if not all fluxes can be assumed to be irreversible? If so, the extreme rays may lose these properties. Moreover, a set of vectors holding the three properties simultaneously (P1, P2, and P3) will not exist; there will be sets fulfilling P1 and P2, or P1 and P3, but not P2 and P3 in a general case.
3. Different NetworkBased Pathways
3.1. Extreme Currents
Extreme currents are probably the first attempt to define a set of networkbased pathways [33]. Their computation is based on splitting up each reversible reaction into two irreversible ones. Thus, if fluxes are reordered to separate the irreversible fluxes and the reversible ones the flux space (2) is augmented : The extreme rays of the cone are defined as the extreme currents of P. Notice that is a pointed cone in the positive orthant , so its extreme rays have all of the properties mentioned above (P1–P3). However, lives in a higherdimensional vector space (augmented in one dimension for each split reversible reaction) and the extreme currents lose their properties when they are translated to the original vectorspace.
In fact, it has been recently shown that the set of extreme currents (ECS) coincides with the set of elementary modes, which will be introduced below, when it is translated to the original vectorspace [34]—when computing the ECS a set of spurious cycles appear (pathways formed by the forward and backward reaction of each reversible flux); however, these pathways are not considered meaningful in most applications [35] and they disappear when the ECs are expressed in the original vectorspace
3.2. Elementary Modes
The concept of elementary modes was introduced to extend the property of nondecomposability of the extreme rays (P3) to networks with reversible fluxes [7, 8]. Hence, a flux vector e is an elementary mode (EM) if and only if [36] (C1),(C2)there is no nonzero vector such that the support of v supp(v) is a proper subset of the support of e supp(e). In other words, e cannot be decomposed as a positive combination of two “simpler” vectors and in P that contain zero elements wherever e does and include at least one additional zero component each. This condition is the socalled nondecomposability, simplicity, or genetic independence.
Thereby, the set of elementary modes (EMS) is defined as the set of all the nondecomposable vectors in the flux space (P3). This definition implies that the EMS fulfills property P1, as in (3), but also a more restrictive condition due to C2: each flux distribution can always be represented as a nonnegative combination of elementary modes without cancelations [36]: If the sum runs over two or more indices all of the have zero components wherever has zero components and include at least one additional zero each.
That means that the elementary modes are all the simple states, or functional units, that a cell can show (the nondecomposable vectors) and the rest of feasible states can be seen as its strictly aggregated action, that is, its aggregated action without cancelations. The “no cancelation rule” is relevant for several applications of networkbased pathways. The no cancelation rule is what makes it possible to investigate the infinite behaviors that cells can show by simply inspection of the finite set of elementary modes, because there is no possibility of cancelations of reversible fluxes. This allows to answer many interesting questions in an easy manner; consider, for example the following:(i)Which reactions are essential to produce the compound Y? Those that participate in all of the elementary modes producing Y.(ii)Is there a route connecting the educt A with the product Y? Only if there is an elementary mode connecting them.(iii)Which are the capabilities of the network if a reaction is not carrying flux or has been knockedout? The feasible states in these circumstances are only those that result from aggregating, with no cancelations, the elementary modes not involving (i.e., the consequences of not carrying flux can be directly predicted ignoring the elementary modes participated by ).(iv)Which is the optimal yield to produce Y from A? The (stoichiometrically) optimal pathway is the elementary mode consuming A and producing Y with the best yield.
As we will see in subsequent sections, the main difference among networkbased pathways is that all of them satisfy (3), but only the elementary modes satisfy (5), and this fact determines their practical applications.
3.3. Minimal Generators
We have seen that the elementary modes generate the flux space, as in (3), but usually they are not the smallest set satisfying this condition because they have to fulfill the most exigent condition of (5). Which is then the minimal set of vectors that generates P by nonnegative combination? The term minimal generating set (MGS) has been recently coined to refer to this set [37]. It was also shown how to obtain an MGS that is subset of EMS. However, in general there is not a unique minimal generating set: different MGSs may exist within the EMS, and even vectors that are not EMs can be part of an MGS. Both cases will be discussed in following sections. Yet, the concept of the minimal generating set also arises from a different point of view. It is well known that the elementary modes are not systemically independent because it is possible to represent some modes as nonnegative combination of others [5]. Clearly, dependent modes that are not necessary to fulfill (3) can be removed. Thus, any resultant irreducible subset of the elementary modes is a minimal generating set.
In summary, a set of minimal generators fulfill properties P1 and P2, whereas the elementary modes fulfill P1 and P3. The elementary modes include additional nondecomposable vectors to fulfill P3, which are redundant in (3) but necessary in (5).
The fact that an MGS does not fulfill (5) reduces its usability for analysis of the underlying metabolism. Remarkably, the questions mentioned in the previous section cannot be easily addressed using the MGS because the cancelation of reversible fluxes hides simple pathways. For example, the MGS has to be recalculated after a gene deletion, and similar difficulties arise in other applications. The advantage of the MGSs against the EMS is its reduced size: considering the central carbon metabolism of E. coli, the computation of the EMS returns more than 500 000 EMs, whereas an MGS contains around 3000 MGs [34]. This also implies that obtaining the MGS is computationally more efficient. Thereby, the MGS will be preferred in those applications that just require a set of vectors generating the fluxspace. For instance, the MGS has been used to perform phenotype phaseplane analysis [37] and it can be used to extract the minimal connections between extracellular compounds, information that can then be used to develop unstructured, kinetic models [29–31, 38].
3.4. Extreme Pathways
As it happens with the extreme currents, extreme pathways are obtained in an augmented vectorspace [35]; however, only the internal fluxes are decomposed in both forward and backward directions (the exchange fluxes, those that connect internal and external metabolites with onetoone correspondence [4], are kept as reversible). Hence, if fluxes are reordered to separate the irreversible internal fluxes the reversible ones , and the exchange fluxes as , the flux space (2) can be reformulated as follows (where ): In this augmented vectorspace, and only there, the set of extreme pathways (EPs) is a subset of the elementary modes that is systemically independent [5]. The EPs are still capable of generating P, as in (3), because only dependent elementary modes are discarded. However, the extreme pathways are not systemically independent in the original one (and even the ECs, which are equivalent to the EMs, are systemically independent in the augmented space where they are obtained). Therefore, they are not the irreducible subset of the elementary modes in the original vectorspace; that is, they are not the minimal generating set [37]. Unfortunately, this notion was unclear in the literature until recently.
The extreme pathways fulfill property P1, but not P2 nor P3 in the original vectorspace. As it happens with the MGS, the fact that the EPS does not fulfill (5) reduces its usability in certain applications. Their advantage with respect to the EMS is its smaller size, but it must be kept in mind that, in general, the MGS will be smaller than the EPS (and never larger).
Example: Two Different VectorSpaces
Consider the small network depicted in Figure 2, Case A. The three EPs of this network represented in the augmented vectorspace are E1 = (1 0 1 0), E2 = (0 1 0 1), and E3 = (1 1 0 0). These three vectors are systemically independent. However, when translated to the original vectorspace these vectors are E1 = (1 0 1), E2 = (0 1 1) and E3 = (1 1 0), which are not longer systemically independent, since E1 = E2 + E3. Figure 2 also illustrates the systemic dependancy of the EPs.
4. Comparison among NetworkBased Pathways
This section is devoted to the comparison of the networkbased pathways described above: extreme currents, minimal generators, elementary modes and extreme pathways. The case where all of the fluxes are irreversible will be introduced first to contextualize the problem; then, the presence of reversible fluxes will be considered and the differences will become apparent (see Figure 2).
Reference VectorSpace
Hereinafter we consider the original vectorspace as the reference one: all of the generating sets will be expressed as elements of the vectorspace where each flux corresponds to an axis. We choose because it is the original space of the fluxes that connect the metabolites of the network, and thus it is the meaningful one. For instance, in the previous example the EPs expressed in the augmented vectorspace were unable to capture the fact that pathway E1 can be seen as a combination of E2 and E3 (E1 = E2 + E3). Notice also that the relevant difference between equations (3) and (5), which depends on the cancelation of reversible fluxes, cannot be easily observed in the augmented vectorspaces. Since ECs and EPs are computed in augmented vectorspaces, once obtained, they have to be translated to , simply merging again the decomposed reversible fluxes. This process also removes the spurious cycles, those pathways formed only by the forward and backward reaction of each reversible flux and appearing as EPs and ECs in the augmented vectorspaces.
4.1. Case 1: All Fluxes Are Irreversible
As explained in a previous section, when all of the reactions are irreversible, the flux space P is a convex cone that satisfies two conditions: (a) it is in the positive orthant and (b) it is a pointed cone.
Condition (b) implies that P can be generated by nonnegative combination of its extreme rays (3) (more details below). In fact, the extreme rays always belong to every generating set because by definition they cannot be generated by nonnegative combination of other vectors within the cone (see glossary). Thus, if the extreme rays are able to generate the cone, as it happens in this case, they are necessarily the minimal generating set. On the other hand, the extreme rays are always nondecomposable vectors of P (since they cannot be generated by nonnegative combination). Moreover, condition (a) implies that the intersections of the cone with the (positive or negative) axis of the vectorspace, which are potential nondecomposable vectors, cannot be interior points of P. Thus, the extreme rays will be all the nondecomposable vectors in P.
These two conditions imply that in this case the extreme rays are not only the minimal generating set of the flux space (P1 and P2), but also the set of all nondecomposable vectors (P3). Since the ECs and the EPs are the extreme rays of two cones defined in augmented vectorspaces where the reversible fluxes are decomposed, it is obvious that, if there are no reactions to be decomposed, the ECs and EPs are the extreme rays of the original cone P. Therefore the following is maintained.
Rule. If all fluxes are irreversible, all the generating sets are equivalent, EMS = ECS = EPS = MGS, and coincide with the extreme rays of the flux space P.
4.2. Case 2: There Are Reversible Fluxes
Now we consider the situation where certain fluxes are reversible. The flux space P is still a convex cone, but it is not necessarily in the positive orthant R^{+} and it can be nonpointed. If one or more reversible reactions are effectively reversible—that is, both forward and backward directions can be realized by flux distributions—the cone will not be in the positive orthant (otherwise P would remain a pointed one in the positive orthant as in Case ). Then, two situations are possible: Case A, the cone is pointed, and Case B, it is not.
Consider the lineality space of P, defined as lin.space It represents the linear subspace contained in the cone and allows to characterize the cone as follows: is pointed if lin.space otherwise nonpointed. Hence, P will be a nonpointed cone if a vector x and its opposite –x exist in P. These vectors would involve only reversible fluxes and represent reversible vectors that can operate in both directions. Thus P is nonpointed cone if and only if it contains a reversible vector. It is also possible to check whether a cone is pointed inspecting K, the kernel of N, arranged in a suitable way (see [37] for details).
The more important consequence of this classification is the following: a pointed cone P can be generated by nonnegative combination of its extreme rays, but this no longer true for a nonpointed one. A nonpointed cone still can be generated by nonnegative combination, but a unique MGS will not exist.
4.3. Case 2A: Reversible Fluxes but Not Reversible Vectors
If there are reversible fluxes but not a reversible vector, the fluxspace P is still a pointed cone and it can be generated by its extreme rays [39]. As explained above, if the extreme rays generate the cone, they are necessarily the minimal generating set because they belong to every generating set by definition.
Rule. If the flux space P does not contain a reversible vector, a unique MGS exists and it coincides with the extreme rays of P.
However, if there are reversible fluxes, and they are effectively used in both directions, the cone is not restricted to the positive orthant R^{+}. This implies that the intersections of vectorspace axis with the cone will be nondecomposable vectors of P. That is, there are nondecomposable vectors in P that are not extreme rays. The EMS sill contains the extreme rays, which are always nondecomposable, but could also contain other nondecomposable vectors. Notice that these extra EMs are necessary to generate the flux space P without cancelations (5), but can be redundant to fulfill (3).
Rule. The EMS (ECS) is always a superset of the extreme rays of the flux space P. If there are reversible fluxes, more EMs than extreme rays may exist.
By Rules 2 and 3 it follows that, if the flux space P does not contain a reversible vector, the MGS is a subset of the EMS. Moreover, those EMs not belonging to the MGS will be systemically dependent and the MGS will be the unique irreducible subset of the EMS.
Rule. If the flux space P does not contain a reversible vector, the unique MGS is the irreducible subset of the EMS. It can be extracted from the EMS selecting the systemically independent vectors (see the appendix).
This property was incorrectly assigned to the extreme pathways in the past, but these are systemically independent only in an augmented vectorspace and not in the original one (see example below). The EPs are the extreme rays of the cone obtained when the internal, reversible reactions are split, whereas the EMs (ECs) are the extreme rays of the cone obtained when all of the reversible reactions are split. This difference determines the relationship among the concepts (Figure 3).
Rule. If the flux space P does not contain a reversible vector, the EPS can be a subset of the EMS, but in general it is not the MGS. That is, EMS (ECS) EPS MGS, and the following two particular cases exist.(a)If all exchange fluxes are irreversible, EMS (ECS) = EPS.(b)If all internal fluxes are irreversible, EPS = MGS.The two rules can be rephrased as follows(a)EPS can be a proper subset of the EMS ⇔ there are reversible exchange fluxes.(b)MGS can be a proper subset of the EPS ⇔ there are reversible internal fluxes.
Proof Outline
(a) If all of the reversible fluxes are internal, the EPs and the ECs (EMs) are the extreme rays of the same cone. (b) If all of the internal fluxes are irreversible, the EPs are the extreme rays of the original cone, which coincide with the extreme rays due to Rule 2.
4.4. Case B: Reversible Fluxes and a Reversible Vector
If the reversible fluxes form a reversible vector, the convex cone is nonpointed. A nonpointed cone can be represented as where H is the linear space lin.space(), and Q is a pointed subcone, with Q H^{⊥} (H^{⊥} denotes the orthogonal complement of H). In fact, this is the general representation of a convex polyhedral cone and Cases and 2A are particular cases where H = . Thus, a nonpointed cone can be generated as follows [39]: where are the “irreversible” generating vectors, for which its opposites are not contained in and are the “reversible” ones, for which its opposite is also contained in Vectors must form a base of H, whereas vectors generate the subcone Q. Notice that can still be generated by nonnegative combination, as in (3), using , , and as generating vectors. Unfortunately, there is a price to pay for the cone being nonpointed: the set of minimal generating vectors is not unique anymore.
In fact, a minimal generating set of is obtained choosing an arbitrary base of H, and taking one arbitrary ray from each minimal proper face of the cone [39]. When the cone is pointed, there are no vectors and the minimal proper faces are the extreme rays, so they are uniquely defined.
The extreme rays of will be present in any generating set—EMS, EPS, or an MGS—because they cannot be represented as nonnegative combination of other vectors in However, they are insufficient to generate a nonpointed cone, they could even not exist (e.g., if all fluxes are reversible, the cone is an dimensional vectorspace generated only by vectors and ). Additional vectors and must be combined with the extreme rays to form an MGS, but the choice is not unique.
Rule. If the flux space contains a reversible vector, its extreme rays are not a complete generating set and there is not a unique MGS.
However, it is still possible to define a MGS containing only nondecomposable vectors, and thus being a subset of the EMS. This kind of MGS can be obtained with a lexicosmallest representation [40] or extracted from the set of EMs, as explained in the appendix.
Rule. If the flux space contains a reversible vector, an irreducible subset of the EMS constitutes an MGS formed only with nondecomposable vectors.
Notice that other MGSs exist. Indeed, even more than one MGS formed with different nondecomposable vectors may exist, since there is not necessarily a unique irreducible subset of EMS. Both situations will be illustrated in subsequent examples.
With respect to the EPS, Rule 5 should be rephrased recalling that the MGS is no longer unique. Moreover, since a reversible vector will be (a) always participated by at least one internal flux—a reversible vector only with external fluxes has little sense and (b) in most cases also participated by external ones (except that if all of the reversible vectors are futile cycles), a common situation arises where EMS (ECS) EPS an MGS.
Rule. If the fluxspace contains a reversible vector, the EPS can be a subset of the EMS, but in general the EPS is not an MGS. The most common case will be EMS (ECS) EPS an MGS.
4.5. Examples
Some examples will be used to illustrate the different cases described above. The first examples (1 to 5) use a simple network taken from Papin et al. [5]. The network has 6 reactions—3 internal and 3 exchange—and three metabolites, so it has 3 degrees of freedom. If all of the reactions were reversible, the kernel of N would provide a basis of the flux space formed by three reversible vectors. Herein we consider five cases where different reactions are irreversible (results are depicted in Figure 4).
Example 1. In the first example all fluxes are assumed to be irreversible (Case ). In this case, the flux space is a pointed cone in and all of the networkbased pathways—ECS, EMS, EPS, and MGS—are equivalent.
Example 2. Now the exchange flux is assumed to be reversible. This example corresponds to Case A (the flux space is a pointed cone not in R^{+}). In this case the EMS can be a superset of the MGS, as indeed happens in this example: EM4 is systemically dependent (EM4 = MG1 + MG2), so it is an EM but not a MG. On the other hand, the EPS is equal to the MGS because the internal fluxes are all irreversible. EM4 is not an EP because the reversible flux being cancelled in MG1 + MG2 is an exchange, so EM4 is systemically dependent in the vectorspace where EPs are computed.
Example 3. In this third example the exchange flux and the internal flux v_{2} are reversible. This is a general case and therefore, EMS EPS MGS. EM5 is neither an EP nor an MG (EM5 = MG1 + MG2). EM4 is not a MG (EM4 = MG3 + MG2), but it is an EP; one of the fluxes cancelled in MG3 + MG2 is an internal flux, so this cancelation cannot be done in the augmented vectorspace where the EPs are computed.
Example 4. In this example only two internal fluxes, and are reversible. Again, the EMS is a superset of the MGS: EM4 is not an MG because it is systemically dependent (EM4 = MG3 + MG2). On the other hand, as all of the reversible fluxes are internal, the EPs and the EMs are necessarily equivalent.
Example 5. Now there are four reversible fluxes— and — that define a reversible vector. This corresponds to Case B, where the flux space is a nonpointed cone. There are 7 EMs and 5 of them are also EPs. The two vectors that form the reversible vector are extreme rays in this example. To form an MGS they need to be combined with 2 other vectors, but the choice is not unique. For instance, 2 subsets of EMs are minimal generating sets, MGS1 and MGS2.
Example 6. Klamt and Stelling use a simple example, referred to as N2 in their article, to investigate the relationship between the EMS and the EPS [4]. This network has 9 reactions (3 exchanges) and 6 metabolites. After computing the EMS, the EPS, and the MGS, it turns out that there are 8 EMs and 5 EPs (the extra EM9/EP6 in [4] disappears in the original vectorspace because it is a spurious cycle caused by decomposing the reversible fluxes). Yet, the MGS contains only 4 vectors, indicating that there is an EP that is not systemically independent: it can be checked by simple inspection that EP1 = EP2 + EP4 (when they are represented in the original vectorspace).
Example 7. Another example to be analyzed is the small network used by Schilling et al. [35]. We obtained 7 EMs and the 5 relevant EPs given in the paper. Again, the EPs are not systemically independent when translated to the original vectorspace (EP2 = EP3 + EP5) and 4 vectors are sufficient to form an MGS. It turns out that the MGS is not unique because there is a reversible vector in the fluxspace (in fact, the reversible vector defines two EPs: EP3 and EP4 use the same reactions but in opposite directions).
Example 8. We have also analyzed the metabolic network of CHO cells given in [31]. The network has 24 reactions (9 reversible) and 18 internal metabolites, so it has 6 degrees of freedom. There are 18 EMs and 8 EPs, but only 6 vectors form the unique MGS (see supplementary file, Figure in supplementry material available online at http://dx.doi.org/10.1155/2010/753904). The metabolic pathways that correspond to the MGs are given in the supplementary file, Figure .
5. Conclusions
The purpose of networkbased pathways analysis is to identify a finite set of systemic pathways in a metabolic network, and then use these pathways to study the cell metabolism. In this paper four similar definitions of networkbased pathways have been compared.
We have seen that all of the flux states of a given metabolic network can be represented as an aggregation of flux through its elementary modes, which are all the simple, or nondecomposable, pathways in the network. Nevertheless, the set of elementary modes is not the smallest set of pathways fulfilling this property; this role corresponds to the socalled minimal generating sets. In certain cases there is a unique minimal generating set, but in general there are several alternatives. Interestingly, the set of elementary modes can be reduced by eliminating modes that are systemically dependent, resulting in a minimal generating set formed only with elementary modes. It has been also highlighted that, contrarily to what has sometimes been stated, the extreme pathways are not the minimal generating set, because they are usually systemically dependent in the original vectorspace.
The minimal generating sets can be of use in applications where a set of generating vectors are required. In these cases they will be preferred due to its reduced size and because their computation is more efficient. For instance, minimal generators are suitable for extracting the fundamental connections between extracellular compounds, information that can be used to develop unstructured, kinetic models [29–31, 38]. However, the analysis of the elementary modes is more powerful. The fact that the set of elementary modes comprises all of the simple pathways in the network—its functional states—makes it possible to investigate the infinite behaviors that cells can show by simply inspecting them. This makes it easy to answer several questions: which reactions are essential to produce a certain compound, which will be the capabilities of the network if a reaction is knockout, and so forth. Answering these questions using the minimal generators or the extreme pathways may be difficult because one has to take into account the possible cancelations of reversible fluxes.
Significant efforts are being done to improve networkbased pathways analysis, particularly in the context of genomescale metabolic network, where their more critical limitation appears: when the number of reactions in the network grows, the number of pathways dramatically increases, reducing understandability and even becoming not computable [5, 6]. Recent works have improved the computation algorithms [41, 42], and proposed methods to get particular subsets of pathways [43] and to decompose large networks in modules [44, 45]. New concepts of pathways have been also recently introduced. Kaleta et al. have introduced “elementary flux patterns”, which explicitly takes into account possible steadystates fluxes through a genomescale network when analyzing pathways through a subsystem, thus allowing the application of many (not all) elementarymodebased tools to genomescale networks [46]. Barrett et al. have used Monte Carlo sampling in conjunction with principal component analysis to obtain a lowdimensional set of pathways generating the flux space of genomescale networks [47].
Most applications of networkbased pathway analysis are found not only in the context of microbial production [9, 11, 12, 17, 20], but also in botany [48, 49] or in biomedicine [50, 51]. The number of applications increases steadily, and we believe that this will continue in the foreseeable future.
Glossary Box
Flux Distribution
The values of every metabolic flux of a given network at a particular (steady) state form a flux distribution.
Flux Space
The space P that contains all of the feasible flux distributions of a given metabolic network is the flux space. The flux space is often a convex polyhedral cone (2).
Convex Polyhedral Cone
A nonempty set of points P is a convex cone if and only if any nonnegative combination of elements from P remains in P. A convex cone P is polyhedral if, for some matrix A, P = . A convex polyhedral cone P is the set of solutions of a homogeneous system of inequalities (or the intersection of finitely many affine halfspaces).
Cone
For brevity, we use the term “cone” to refer to a convex polyhedral cone.
Nonnegative Generation
The Farkas theorem asserts that a convex cone is polyhedral if and only if it is finitely generated. A cone is finitely generated if there exist a set of vectors that generate it by nonnegative combination.
Generating Set
Any set of vectors G in P that generates P by nonnegative combination is a generating set of P. The EMS, the ECS, the EPS, and the MGSs are generating sets of P.
Lineality Space
Let P be a convex polyhedral cone, P = ∈ Then, lin.space(P) = ∈ = is called the lineality space of P. It is the tdimensional linear subspace contained in the cone.
Reversible Vectors
The lineality space, lin.space(P), contains the nonzero vectors r in P whose opposite is also in P. These involve only reversible fluxes and represent flux distributions that can operate in both directions. They can be called reversible vectors.
Pointed Cone
A convex polyhedral cone P is said to be pointed if lin.space(P) = In other words, a cone is nonpointed if it contains a reversible vector, and pointed otherwise.
Generation of a Pointed Cone
A pointed cone P can be generated by nonnegative combination of its extreme rays, which is the unique, minimal generating set of P (MGS).
Generation of a Nonpointed Cone
A nonpointed cone P can still be generated by convex combination of a set of vectors, but there is no longer a unique MGS.
Extreme Rays or Edges
A vector d is a ray of the convex polyhedral cone P if for all for each . If a ray d cannot be expressed as nonnegative combination of other rays in it is an extreme ray. In metabolic pathway analysis, extreme rays are important because (i) if the cone is pointed, the extreme rays are the unique MGS. In the general case, the extreme rays (ii) belong to every generating set of P, and (iii) they are always nondecomposable.
Nondecomposability
Given a cone P, a vector is nondecomposable if it cannot be represented as a positive combination of two vectors and in P that contain zero elements wherever n does and include at least one additional zero each. These vectors represent the simple states or functional units that a cell can show; the rest of feasible states can be seen as its aggregated action without cancelations. This property is relevant in several applications. All the generating set may contain nondecomposable vectors, but only the EMS is the set of all of the nondecomposable vectors in P.
Systemic Independence
A set of vectors I are systemically independent if no vector in I can be represented as a nonnegative combination of others. The extreme rays are always a systemically independent set of vectors.
Irreducible Subset
Given a generating set G of P that is not systemically independent, every smallest subset of G that generates G, and therefore P, is an irreducible subset of G. If the cone is pointed, there is a unique irreducible subset for every generating set and it coincides with the extreme rays of the cone, but if the cone is nonpointed, several irreducible subsets may exist.
(Flux) VectorSpace
The term (flux) vectorspace refers to the space with the metabolic fluxes as axis. The original flux vectorspace has dimensions n (n is number of reaction in the network), but some networkbased pathways are computed in auxiliary vectorspaces of higher dimension.
Appendix
Computation of NetworkBased Pathways
The elementary modes can be computed with Metatool [13] and cellNetAnalyzer [52], both running under MATLAB. The extreme pathways can be computed using expa [53]. Minimal generating sets can be obtained using SNA [54], a software package running under Mathematica, or using ccd [55] as reported in [40]. In addition, we describe a simple method to get an MGS from the EMS extracting an irreducible subset.
Extracting an MGS from the EMS
The procedure can be outlined with the following pseudocode: for each elementary mode in E define if (there is no ) then: add to Mendwhere E is the matrix formed with EMs as columns, is the submatrix of E with only columns after i, and M is the matrix collecting the MGs (thus empty on first iteration).
If the cone is pointed, the resultant set is the unique MGS (and coincides with the extreme rays of the cone). Otherwise, it is a nonunique MGS formed with nondecomposable vectors.
Acknowledgments
This research has been partially supported by the Spanish Government (DPI200806880C0301 and A/016560/08). The first author is recipient of a fellowship from the Spanish Ministry of Education and Science (FPU AP20051442).
Supplementary Materials
The Supplementary file contains additional figures for the example of CHO cells.
References
 G. N. Stephanopoulos and A. A. Aristidou, Metabolic Engineering: Principles and Methodologies, Academic Press, San Diego, Calif, USA, 1998.
 B. O. Palsson, Systems Biology: Properties of Reconstructed Networks, Cambridge University Press, Cambridge, Mass, USA, 2006.
 F. Llaneras and J. Picó, “Stoichiometric modelling of cell metabolism,” Journal of Bioscience and Bioengineering, vol. 105, no. 1, pp. 1–11, 2008. View at: Publisher Site  Google Scholar
 S. Klamt and J. O. Stelling, “Two approaches for metabolic pathway analysis?” Trends in Biotechnology, vol. 21, no. 2, pp. 64–69, 2003. View at: Publisher Site  Google Scholar
 J. A. Papin, J. Stelling, N. D. Price, S. Klamt, S. Schuster, and B. O. Palsson, “Comparison of networkbased pathway analysis methods,” Trends in Biotechnology, vol. 22, no. 8, pp. 400–405, 2004. View at: Publisher Site  Google Scholar
 J. Gagneur and S. Klamt, “Computation of elementary modes: a unifying framework and the new binary approach,” BMC Bioinformatics, vol. 5, article 175, 2004. View at: Publisher Site  Google Scholar
 S. Schuster, D. A. Fell, and T. Dandekar, “A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic networks,” Nature Biotechnology, vol. 18, no. 3, pp. 326–332, 2000. View at: Publisher Site  Google Scholar
 S. Schuster, T. Dandekar, and D. A. Fell, “Detection of elementary flux modes in biochemical networks: a promising tool for pathway analysis and metabolic engineering,” Trends in Biotechnology, vol. 17, no. 2, pp. 53–60, 1999. View at: Publisher Site  Google Scholar
 C. H. Schilling and B. Ø. Palsson, “Assessment of the metabolic capabilities of Haemophilus influenzae Rd through a genomescale pathway analysis,” Journal of Theoretical Biology, vol. 203, no. 3, pp. 249–283, 2000. View at: Publisher Site  Google Scholar
 J. Stelling, S. Klamt, K. Bettenbrock, S. Schuster, and E. D. Gilles, “Metabolic network structure determines key aspects of functionality and regulation,” Nature, vol. 420, no. 6912, pp. 190–193, 2002. View at: Publisher Site  Google Scholar
 J. A. Papin, N. D. Price, and B. Ø. Palsson, “Extreme pathway lengths and reaction participation in genomescale metabolic networks,” Genome Research, vol. 12, no. 12, pp. 1889–1900, 2002. View at: Publisher Site  Google Scholar
 N. D. Price, J. A. Papin, and B. Ø. Palsson, “Determination of redundancy and systems properties of the metabolic network of Helicobacter pylori using genomescale extreme pathway analysis,” Genome Research, vol. 12, no. 5, pp. 760–769, 2002. View at: Publisher Site  Google Scholar
 T. Pfeiffer, I. SánchezValdenebro, J. C. Nuño, F. Montero, and S. Schuster, “METATOOL: for studying metabolic networks,” Bioinformatics, vol. 15, no. 3, pp. 251–257, 1999. View at: Publisher Site  Google Scholar
 T. Çakir, B. Kirdar, and K. O. Ülgen, “Metabolic pathway analysis of yeast strengthens the bridge between transcriptomics and metabolic networks,” Biotechnology and Bioengineering, vol. 86, no. 3, pp. 251–260, 2004. View at: Publisher Site  Google Scholar
 M. W. Covert and B. Ø. Palsson, “Constraintsbased models: regulation of gene expression reduces the steadystate solution space,” Journal of Theoretical Biology, vol. 221, no. 3, pp. 309–325, 2003. View at: Publisher Site  Google Scholar
 R. Carlson, D. Fell, and F. Srienc, “Metabolic pathway analysis of a recombinant yeast for rational strain development,” Biotechnology and Bioengineering, vol. 79, no. 2, pp. 121–134, 2002. View at: Publisher Site  Google Scholar
 S. J. van Dien and M. E. Lidstrom, “Stoichiometric model for evaluating the metabolic capabilities of the facultative methylotroph Methylobacterium extorquens AM1, with application to reconstruction of C3 and C4 metabolism,” Biotechnology and Bioengineering, vol. 78, no. 3, pp. 296–312, 2002. View at: Publisher Site  Google Scholar
 S. Klamt and E. D. Gilles, “Minimal cut sets in biochemical reaction networks,” Bioinformatics, vol. 20, no. 2, pp. 226–234, 2004. View at: Publisher Site  Google Scholar
 J. C. Liao, S.Y. Hou, and Y.P. Chao, “Pathway analysis, engineering, and physiological considerations for redirecting central metabolism,” Biotechnology and Bioengineering, vol. 52, no. 1, pp. 129–140, 1996. View at: Publisher Site  Google Scholar
 J.M. Schwartz and M. Kanehisa, “Quantitative elementary mode analysis of metabolic pathways: the example of yeast glycolysis,” BMC Bioinformatics, vol. 7, article 186, 2006. View at: Publisher Site  Google Scholar
 R. Schwarz, P. Musch, A. von Kamp et al., “YANA—a software tool for analyzing flux modes, geneexpression and enzyme activites,” BMC Bioinformatics, vol. 6, article 135, 2005. View at: Publisher Site  Google Scholar
 S. J. Wiback, R. Mahadevan, and B. Ø. Palsson, “Reconstructing metabolic flux vectors from extreme pathways: defining the $\alpha $spectrum,” Journal of Theoretical Biology, vol. 224, no. 3, pp. 313–324, 2003. View at: Publisher Site  Google Scholar
 F. Llaneras and J. Picó, “An interval approach for dealing with flux distributions and elementary modes activity patterns,” Journal of Theoretical Biology, vol. 246, no. 2, pp. 290–308, 2007. View at: Publisher Site  Google Scholar
 J. Forster, A. K. Gombert, and J. Nielsen, “A functional genomics approach using metabolomics and in silico pathway analysis,” Biotechnology and Bioengineering, vol. 79, no. 7, pp. 703–712, 2002. View at: Publisher Site  Google Scholar
 D. A. Beard, S.D. Liang, and H. Qian, “Energy balance for analysis of complex metabolic networks,” Biophysical Journal, vol. 83, no. 1, pp. 79–86, 2002. View at: Google Scholar
 C. H. Schilling, M. W. Covert, I. Famili, G. M. Church, J. S. Edwards, and B. Ø. Palsson, “Genomescale metabolic model of Helicobacter pylori 26695,” Journal of Bacteriology, vol. 184, no. 16, pp. 4582–4593, 2002. View at: Publisher Site  Google Scholar
 T. Dandekar, S. Schuster, B. Snel, M. Huynen, and P. Bork, “Pathway alignment: application to the comparative analysis of glycolytic enzymes,” Biochemical Journal, vol. 343, no. 1, pp. 115–124, 1999. View at: Publisher Site  Google Scholar
 A. CornishBowden and M. L. Cárdenas, “From genome to cellular phenotype—a role for metabolic flux analysis?” Nature Biotechnology, vol. 18, no. 3, pp. 267–268, 2000. View at: Publisher Site  Google Scholar
 J. Gao, V. M. Gorenflo, J. M. Scharer, and H. M. Budman, “Dynamic metabolic modeling for a MAb bioprocess,” Biotechnology Progress, vol. 23, no. 1, pp. 168–181, 2007. View at: Publisher Site  Google Scholar
 A. P. Teixeira, C. Alves, P. M. Alves, M. J. T. Carrondo, and R. Oliveira, “Hybrid elementary flux analysis/nonparametric modeling: application for bioprocess control,” BMC Bioinformatics, vol. 8, article 30, 2007. View at: Publisher Site  Google Scholar
 A. Provost, G. Bastin, S. N. Agathos, and Y.J. Schneider, “Metabolic design of macroscopic bioreaction models: application to Chinese hamster ovary cells,” Bioprocess and Biosystems Engineering, vol. 29, no. 56, pp. 349–366, 2006. View at: Publisher Site  Google Scholar
 R. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, USA, 1970.
 B. L. Clarke, “Stoichiometric network analysis,” Cell Biophysics, vol. 12, no. 1, pp. 237–253, 1988. View at: Publisher Site  Google Scholar
 C. Wagner and R. Urbanczik, “The geometry of the flux cone of a metabolic network,” Biophysical Journal, vol. 89, no. 6, pp. 3837–3845, 2005. View at: Publisher Site  Google Scholar
 C. H. Schilling, D. Letscher, and B. Ø. Palsson, “Theory for the systemic definition of metabolic pathways and their use in interpreting metabolic function from a pathwayoriented perspective,” Journal of Theoretical Biology, vol. 203, no. 3, pp. 229–248, 2000. View at: Publisher Site  Google Scholar
 S. Schuster, C. Hilgetag, J. H. Woods, and D. A. Fell, “Reaction routes in biochemical reaction systems: algebraic properties, validated calculation procedure and example from nucleotide metabolism,” Journal of Mathematical Biology, vol. 45, no. 2, pp. 153–181, 2002. View at: Publisher Site  Google Scholar
 R. Urbanczik and C. Wagner, “An improved algorithm for stoichiometric network analysis: theory and applications,” Bioinformatics, vol. 21, no. 7, pp. 1203–1210, 2005. View at: Publisher Site  Google Scholar
 A. Provost and G. Bastin, “Dynamic metabolic modelling under the balanced growth condition,” Journal of Process Control, vol. 14, no. 7, pp. 717–728, 2004. View at: Publisher Site  Google Scholar
 A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Amsterdam, The Netherlands, 1998.
 A. Larhlimi and A. Bockmayr, “A new constraintbased description of the steadystate flux cone of metabolic networks,” Discrete Applied Mathematics, vol. 157, no. 10, pp. 2257–2266, 2009. View at: Publisher Site  Google Scholar
 S. Klamt, J. Gagneur, and A. von Kamp, “Algorithmic approaches for computing elementary modes in large biochemical reaction networks,” Systems Biology, vol. 152, no. 4, pp. 249–255, 2005. View at: Publisher Site  Google Scholar
 M. Terzer and J. Stelling, “Largescale computation of elementary flux modes with bit pattern trees,” Bioinformatics, vol. 24, no. 19, pp. 2229–2235, 2008. View at: Publisher Site  Google Scholar
 L. F. de Figueiredo, A. Podhorski, A. Rubio et al., “Computing the shortest elementary flux modes in genomescale metabolic networks,” Bioinformatics, vol. 25, no. 23, pp. 3158–3165, 2009. View at: Publisher Site  Google Scholar
 S. Schuster, T. Pfeiffer, F. Moldenhauer, I. Koch, and T. Dandekar, “Exploring the pathway structure of metabolism: decomposition into subnetworks and application to Mycoplasma pneumoniae,” Bioinformatics, vol. 18, no. 2, pp. 351–361, 2002. View at: Google Scholar
 J.M. Schwartz, C. Gaugain, J. C. Nacher, A. de Daruvar, and M. Kanehisa, “Observing metabolic functions at the genome scale,” Genome Biology, vol. 8, no. 6, article R123, 2007. View at: Publisher Site  Google Scholar
 C. Kaleta, L. F. De Figueiredo, and S. Schuster, “Can the whole be less than the sum of its parts? Pathway analysis in genomescale metabolic networks using elementary flux patterns,” Genome Research, vol. 19, no. 10, pp. 1872–1883, 2009. View at: Publisher Site  Google Scholar
 C. L. Barrett, M. J. Herrgard, and B. Ø. Palsson, “Decomposing complex reaction networks using random sampling, principal component analysis and basis rotation,” BMC Systems Biology, vol. 3, article 30, 2009. View at: Publisher Site  Google Scholar
 M. G. Poolman, D. A. Fell, and C. A. Raines, “Elementary modes analysis of photosynthate metabolism in the chloroplast stroma,” European Journal of Biochemistry, vol. 270, no. 3, pp. 430–439, 2003. View at: Publisher Site  Google Scholar
 R. Steuer, A. N. Nesi, A. R. Fernie, T. Gross, B. Blasius, and J. Selbig, “From structure to dynamics of metabolic pathways: application to the plant mitochondrial TCA cycle,” Bioinformatics, vol. 23, no. 11, pp. 1378–1385, 2007. View at: Publisher Site  Google Scholar
 J.J. Zhong, “Plant cell culture for production of paclitaxel and other taxanes,” Journal of Bioscience and Bioengineering, vol. 94, no. 6, pp. 591–599, 2002. View at: Publisher Site  Google Scholar
 R. P. Nolan, A. P. Fenley, and K. Lee, “Identification of distributed metabolic objectives in the hypermetabolic liver by flux and energy balance analysis,” Metabolic Engineering, vol. 8, no. 1, pp. 30–45, 2006. View at: Publisher Site  Google Scholar
 S. Klamt, J. Stelling, M. Ginkel, and E. D. Gilles, “FluxAnalyzer: exploring structure, pathways, and flux distributions in metabolic networks on interactive flux maps,” Bioinformatics, vol. 19, no. 2, pp. 261–269, 2003. View at: Publisher Site  Google Scholar
 S. L. Bell and B. Ø. Palsson, “Expa: a program for calculating extreme pathways in biochemical reaction networks,” Bioinformatics, vol. 21, no. 8, pp. 1739–1740, 2005. View at: Publisher Site  Google Scholar
 R. Urbanczik, “SNA—a toolbox for the stoichiometric analysis of metabolic networks,” BMC Bioinformatics, vol. 7, article 129, 2006. View at: Publisher Site  Google Scholar
 K. Fukuda and A. Prodon, “Double description method revisited,” in Combinatorics and Computer Science, vol. 1120, pp. 91–111, Springer, London, UK, 1996. View at: Google Scholar
Copyright
Copyright © 2010 Francisco Llaneras and Jesús Picó. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.