BACKGROUND
flux balance analysis is becoming a well developed and frequently used theoretical tool to study the capabilities of large stoichiometric networks  <cit> .
flux balance analysis relies on several assumptions that essentially impose constraints on the allowable states of a network.
ideally, these constraints are derived from fundamental physical and chemical principles so that the physically realistic states of a network can be accurately identified and the unrealistic states ignored.
ensuring the conservation of mass can be achieved in a relatively straightforward manner, but it is much more challenging to incorporate the conservation of energy  <cit> .
methods that rely on the identification of steady state reaction cycles have been developed to achieve this  <cit> .
knowledge of these cycles can be used to constrain the direction or magnitude of certain fluxes to prevent the occurrence of thermodynamically inconsistent network states.
the incorporation of energetic constraints in flux balance analysis is not the only motivation to identify cycles.
cycles may also point towards important aspects of network function.
for instance, it has been proposed that cycles in metabolic networks can affect the sensitivity and robustness of network function and allow for regulation of biochemical pathways  <cit> .
in signal transduction networks, which are also stoichiometric in nature  <cit> , cycles may allow for feedback.
feedback is known to be an important property of signal transduction, and it has been shown to result in a variety of complex and potentially useful biochemical behaviors  <cit> .
two algorithms have been explicitly described for the identification of steady state cycles in stoichiometric networks.
schilling, letscher, and palsson  described the first of these in  <dig>  <cit> .
the slp algorithm first defines a network of internal and exchange reactions.
internal reactions are those that are actually being studied.
for metabolic networks, for example, the internal reactions are those that occur in or around the cell, such as reactions involved in glycolysis, respiration, transport of metabolites across cellular membranes, etc.
exchange reactions are pseudo-reactions that are used to supply  chemical species to  the reaction system.
the flux, or rate, of each internal reaction is constrained to be positive, while the fluxes of exchange reactions may be left unconstrained.
if reversible reactions are present in the network, they are broken apart into a pair of unidirectional forward-reverse reactions, each with its own flux.
these reactions are used to construct a stoichiometry matrix s which is used to formulate the equation sv =  <dig>  where v is a vector of fluxes of all reactions in the network.
the solutions to this equation represent the allowable steady states of the network, where steady refers to the fact that the concentrations of internal chemical species remain constant.
the slp algorithm then identifies all of the extreme pathways of a network, which are a unique set of flux vectors whose superposition can generate all steady-state fluxes in a network that do not violate the principle of mass conservation.
the extreme pathways are then categorized based on the types of active reactions they contain.
we use the word cycles from this point forward to refer exclusively to internal cycles, that is type iii extreme pathways, which are the extreme pathways that do not contain active exchange reactions .
type iii extreme pathways are also elementary flux modes  <cit>  and extremal currents  <cit> .
the identification of extreme pathways is equivalent to computing the set of extreme rays of a convex cone  <cit> , which is known to be an np-hard problem  <cit> .
this computational complexity limits the size of networks for which the slp algorithm can be used  <cit> , although numerous algorithmic improvements have been recently made in an effort to alleviate this problem  <cit> .
mahadevan and schilling  very briefly described the second algorithm for cycle identification in  <dig>  <cit> .
in this approach, the network and its corresponding stoichiometry matrix are defined in the same way as for the slp algorithm.
the ms algorithm, however, uses a unique property of cycles to assist with their detection.
if a network does not contain exchange reactions, and the fluxes of all internal reactions are constrained to the interval [ <dig>  ∞), the only reactions in the network capable of functioning will be those that participate in cycles .
the ms algorithm takes advantage of this fact by using linear programming to determine the maximum flux of each reaction in the network.
all of the reactions with unbounded fluxes are then used to create a sub-network of the original network.
every reaction in this sub-network necessarily participates in a cycle of the original network .
the slp algorithm is then applied to the sub-network to identify all of its extreme pathways, which are necessarily the complete set of cycles in the original network .
since the sub-network supplied to the slp algorithm is potentially smaller than the original network, the identification of cycles in larger networks may become possible.
in this paper, we describe a new algorithm, which we refer to here as the ww algorithm.
the ww algorithm is an extension of the ms algorithm, and it can reduce the size of the sub-network supplied to the slp algorithm far beyond that of the ms algorithm.
we also measure and compare, for the first time, the performances of all three algorithms using five genome-scale metabolic networks.
RESULTS
the ww algorithm
step  <dig>  ensure that the network does not contain exchange reactions, and constrain the flux of each internal reaction to the interval [ <dig>  ∞).
step  <dig>  let u denote an empty set, and for each reaction r in the network, do the following:
step i. by pair-wise comparison, identify all reactions in the network that are the reverse of r.
step ii.
for each of the reverse reactions identified in step i, constrain its flux to be zero.
step iii.
determine if the flux of reaction r can assume a value other than zero, while still satisfying all currently defined constraints.
if so, add reaction r to the set u.
step iv.
for each of the reverse reactions identified in step i, restore the constraint on its flux to [ <dig>  ∞).
step  <dig>  identify the extreme pathways in the network defined by the reactions contained in the set u.
step  <dig>  by pair-wise comparison, identify each pair of internal forward-reverse reactions, rf and rr, in the stoichiometric network.
a particular rf-rr pair forms a single type iii extreme pathway .
step  <dig>  combine the results of steps  <dig> and  <dig> to obtain the set of all cycles present in the network .
step  <dig> ensures that the only extreme pathways present in the network are of type iii, since all other types of extreme pathways must contain active exchange reactions.
step  <dig> is used to identify all reactions that participate in cycles composed of three or more reactions.
under these circumstances, the fluxes of reactions that participate in such cycles can assume any value on the interval [ <dig>  ∞), and the fluxes of reactions that do not participate in such cycles must be zero.
any technique capable of making this distinction, such as linear programming, can be used during this step.
the reason for this property is that if a reaction r only participates in cycles composed of two reactions, it must be inactive when its reverse reactions are constrained to be inactive.
in step  <dig>  a sub-network is created that is composed of the reactions identified in step  <dig>  and an algorithm is applied to that network to identify the type iii extreme pathways it contains.
that algorithm could be the slp algorithm, or another that achieves the same result.
step  <dig> is used to identify all of the extreme pathways composed of only two reactions.
this could also be accomplished during step  <dig> i, but it is listed separately here for the sake of clarity.
the appendix contains a more explicit justification of the principle behind the ww algorithm.
there are two key differences between the ww and ms algorithms.
firstly, the ms algorithm, as it is defined, individually maximizes the flux of each reaction in a network.
flux maximization can also be performed to accomplish step  <dig> iii of the ww algorithm, but other  techniques could be used as well.
secondly, the ms algorithm creates sub-networks composed of all of the reactions in a network that participate in cycles.
the ww algorithm, however, creates sub-networks composed only of those reactions that participate in cycles composed of three or more reactions.
consequently, the ww algorithm can sometimes produce sub-networks drastically smaller than those of the ms algorithm, which is demonstrated below.
performance comparisons
we tested the performance of the ms, slp, and ww algorithms for genome-scale metabolic networks from four different microbes and from homo sapiens , comprising between  <dig> and  <dig> chemical species, and between  <dig> and  <dig> reactions.
our results show that both execution time efficiency  and memory efficiency  were substantially different for the three algorithms, with the ww algorithm being more efficient than the ms algorithm, which was more efficient than the slp algorithm.
these performance differences are described in detail in the following sections.
preprocessing
both the ww and ms algorithms use a preprocessing procedure to reduce the size of the network before identification of cycles is attempted.
for both algorithms, the time and memory consumption of the preprocessing phase increases as network size increases, although not substantially; and ww preprocessing consumes more time and moderately more memory than ms preprocessing .
extreme pathway identification
the time and memory consumption of the ms, slp, and ww algorithms during extreme pathway identification were quite different.
to begin with, the slp algorithm was unable to complete execution with the e. coli, s. cerevisiae, and h. sapiens networks due to memory exhaustion.
this also occurred for both the ms and ww algorithms with the h. sapiens network.
therefore, at least for the hardware and software configurations used for these analyses, memory efficiency during extreme pathway identification was the most important factor for achieving successful computation.
for the microbial networks, the maximum memory consumption of the ms algorithm was much less than that of the slp algorithm, and the memory consumption of the ww algorithm was less than that of the ms algorithm .
the memory usage of both the ms and slp algorithms increased substantially with increasing network size, but in contrast, the memory usage of the ww algorithm changed little as the size of the microbial networks increased .
similar trends were observed for time efficiency, as well .
the observed performance differences of extreme pathway identification can best be explained by noting the reduction of network sizes achieved during the preprocessing phases of the ms and ww algorithms.
the slp algorithm uses the entire network, whose numbers of reactions and metabolites are shown in table  <dig>  the ms algorithm uses sub-networks containing only reactions that participate in cycles, but the ww algorithm uses sub-networks containing only reactions that participate in cycles that are composed of more than two reactions.
the reduction in size between the full network and the sub-network used by the ww algorithm is dramatic, spanning more than an order of magnitude for each of the microbial networks .
for these networks, the majority of cycles are composed of only two reactions , allowing the ww algorithm to produce much smaller sub-networks than the ms algorithm.
this greatly reduces the computational effort required of the slp algorithm, resulting in better performance.
overall performance
although the ww preprocessing step consumes more time and memory than ms preprocessing, the time and memory efficiency of identifying extreme pathways during the ww algorithm is dramatically better.
consequently, the overall execution time of the ww algorithm is substantially less than the ms algorithm, and the memory consumption is also significantly reduced during the phase of the computation that is most memory-intensive and most susceptible to combinatorial explosion.
caveats
there are certain extreme cases where these performance differences will not persist.
for example, if every reaction in a stoichiometric network participates in a cycle, the ms algorithm will fail to outperform the slp algorithm.
in this situation, the maximum flux of each reaction will be unbounded, resulting in a "sub-network" that is exactly the same as the original.
similarly, if every reaction in a stoichiometric network participates in cycles composed of more than two reactions, neither the ms nor ww algorithm will outperform the slp algorithm.
if all the cycles in a stoichiometric network are composed of more than two reactions, the ww algorithm will fail to outperform the ms algorithm.
if a reaction network does not contain any cycles, the ms algorithm will likely have a performance advantage over the ww algorithm, depending on implementation details.
we note that these extreme scenarios are not realistic for genome-scale metabolic networks , the kinds of networks for which application of the ww algorithm would be most fruitful.
if, finally, a network only contains cycles composed of two reactions, the ww algorithm will never make use of the slp algorithm, which eliminates the chance of combinatorial explosion and most likely provides further dramatic performance improvements over the ms algorithm.
it should also be noted that the algorithmic performances described herein are dependent upon implementation details and the choice of underlying algorithms.
other software and algorithms  <cit> , for example, could be used to identify extreme pathways, which would certainly change the time and memory requirements of these computations.
additionally, flux maximization was performed by both implementations of the ww and ms algorithms during the preprocessing phase.
as mentioned above, replacing flux maximization with another technique, such as an infeasibility test, would also change the time and memory requirements of this portion of the algorithms.
CONCLUSIONS
the ww algorithm consistently achieves significant performance improvements over both the ms and slp algorithms for the microbial networks we examined.
for these networks, the execution time and maximum memory consumption of the ww algorithm are both smaller by multiple factors.
the scaling behavior of the ww algorithm as a function of network size is also preferable to both the ms and slp algorithms.
due to combinatorial explosion during extreme pathway identification, however, all of the algorithms fail to identify the cycles within the human metabolic network.
at this point in time, the ww algorithm appears to be the best choice for identifying steady state cycles in large, real-world stoichiometric networks, although additional algorithmic innovation is clearly desirable.

 flux balance analysis is becoming a well developed and frequently used theoretical tool to study the capabilities of large stoichiometric networks. flux balance analysis relies on several assumptions that essentially impose constraints on the allowable states of a network. ideally, these constraints are derived from fundamental physical and chemical principles so that the physically realistic states of a network can be accurately identified and the unrealistic states ignored. ensuring the conservation of mass can be achieved in a relatively straightforward manner, but it is much more challenging to incorporate the conservation of energy. methods that rely on the identification of steady state reaction cycles have been developed to achieve this. knowledge of these cycles can be used to constrain the direction or magnitude of certain fluxes to prevent the occurrence of thermodynamically inconsistent network states. the incorporation of energetic constraints in flux balance analysis is not the only motivation to identify cycles. cycles may also point towards important aspects of network function. for instance, it has been proposed that cycles in metabolic networks can affect the sensitivity and robustness of network function and allow for regulation of biochemical pathways. in signal transduction networks, which are also stoichiometric in nature, cycles may allow for feedback. feedback is known to be an important property of signal transduction, and it has been shown to result in a variety of complex and potentially useful biochemical behaviors. two algorithms have been explicitly described for the identification of steady state cycles in stoichiometric networks. schilling, letscher, and palsson described the first of these in. the slp algorithm first defines a network of internal and exchange reactions. internal reactions are those that are actually being studied. for metabolic networks, for example, the internal reactions are those that occur in or around the cell, such as reactions involved in glycolysis, respiration, transport of metabolites across cellular membranes, etc. exchange reactions are pseudo-reactions that are used to supply chemical species to the reaction system. the flux, or rate, of each internal reaction is constrained to be positive, while the fluxes of exchange reactions may be left unconstrained. if reversible reactions are present in the network, they are broken apart into a pair of unidirectional forward-reverse reactions, each with its own flux. these reactions are used to construct a stoichiometry matrix s which is used to formulate the equation sv = where v is a vector of fluxes of all reactions in the network. the solutions to this equation represent the allowable steady states of the network, where steady refers to the fact that the concentrations of internal chemical species remain constant. the slp algorithm then identifies all of the extreme pathways of a network, which are a unique set of flux vectors whose superposition can generate all steady-state fluxes in a network that do not violate the principle of mass conservation. the extreme pathways are then categorized based on the types of active reactions they contain. we use the word cycles from this point forward to refer exclusively to internal cycles, that is type iii extreme pathways, which are the extreme pathways that do not contain active exchange reactions. type iii extreme pathways are also elementary flux modes and extremal currents. the identification of extreme pathways is equivalent to computing the set of extreme rays of a convex cone, which is known to be an np-hard problem. this computational complexity limits the size of networks for which the slp algorithm can be used, although numerous algorithmic improvements have been recently made in an effort to alleviate this problem. mahadevan and schilling very briefly described the second algorithm for cycle identification in. in this approach, the network and its corresponding stoichiometry matrix are defined in the same way as for the slp algorithm. the ms algorithm, however, uses a unique property of cycles to assist with their detection. if a network does not contain exchange reactions, and the fluxes of all internal reactions are constrained to the interval [ ∞), the only reactions in the network capable of functioning will be those that participate in cycles. the ms algorithm takes advantage of this fact by using linear programming to determine the maximum flux of each reaction in the network. all of the reactions with unbounded fluxes are then used to create a sub-network of the original network. every reaction in this sub-network necessarily participates in a cycle of the original network. the slp algorithm is then applied to the sub-network to identify all of its extreme pathways, which are necessarily the complete set of cycles in the original network. since the sub-network supplied to the slp algorithm is potentially smaller than the original network, the identification of cycles in larger networks may become possible. in this paper, we describe a new algorithm, which we refer to here as the ww algorithm. the ww algorithm is an extension of the ms algorithm, and it can reduce the size of the sub-network supplied to the slp algorithm far beyond that of the ms algorithm. we also measure and compare, for the first time, the performances of all three algorithms using five genome-scale metabolic networks.  the ww algorithm step ensure that the network does not contain exchange reactions, and constrain the flux of each internal reaction to the interval [ ∞). step let u denote an empty set, and for each reaction r in the network, do the following: step i. by pair-wise comparison, identify all reactions in the network that are the reverse of r. step ii. for each of the reverse reactions identified in step i, constrain its flux to be zero. step iii. determine if the flux of reaction r can assume a value other than zero, while still satisfying all currently defined constraints. if so, add reaction r to the set u. step iv. for each of the reverse reactions identified in step i, restore the constraint on its flux to [ ∞). step identify the extreme pathways in the network defined by the reactions contained in the set u. step by pair-wise comparison, identify each pair of internal forward-reverse reactions, rf and rr, in the stoichiometric network. a particular rf-rr pair forms a single type iii extreme pathway. step combine the results of steps and to obtain the set of all cycles present in the network. step ensures that the only extreme pathways present in the network are of type iii, since all other types of extreme pathways must contain active exchange reactions. step is used to identify all reactions that participate in cycles composed of three or more reactions. under these circumstances, the fluxes of reactions that participate in such cycles can assume any value on the interval [ ∞), and the fluxes of reactions that do not participate in such cycles must be zero. any technique capable of making this distinction, such as linear programming, can be used during this step. the reason for this property is that if a reaction r only participates in cycles composed of two reactions, it must be inactive when its reverse reactions are constrained to be inactive. in step a sub-network is created that is composed of the reactions identified in step and an algorithm is applied to that network to identify the type iii extreme pathways it contains. that algorithm could be the slp algorithm, or another that achieves the same result. step is used to identify all of the extreme pathways composed of only two reactions. this could also be accomplished during step i, but it is listed separately here for the sake of clarity. the appendix contains a more explicit justification of the principle behind the ww algorithm. there are two key differences between the ww and ms algorithms. firstly, the ms algorithm, as it is defined, individually maximizes the flux of each reaction in a network. flux maximization can also be performed to accomplish step iii of the ww algorithm, but other techniques could be used as well. secondly, the ms algorithm creates sub-networks composed of all of the reactions in a network that participate in cycles. the ww algorithm, however, creates sub-networks composed only of those reactions that participate in cycles composed of three or more reactions. consequently, the ww algorithm can sometimes produce sub-networks drastically smaller than those of the ms algorithm, which is demonstrated below. performance comparisons we tested the performance of the ms, slp, and ww algorithms for genome-scale metabolic networks from four different microbes and from homo sapiens, comprising between and chemical species, and between and reactions. our results show that both execution time efficiency and memory efficiency were substantially different for the three algorithms, with the ww algorithm being more efficient than the ms algorithm, which was more efficient than the slp algorithm. these performance differences are described in detail in the following sections. preprocessing both the ww and ms algorithms use a preprocessing procedure to reduce the size of the network before identification of cycles is attempted. for both algorithms, the time and memory consumption of the preprocessing phase increases as network size increases, although not substantially; and ww preprocessing consumes more time and moderately more memory than ms preprocessing. extreme pathway identification the time and memory consumption of the ms, slp, and ww algorithms during extreme pathway identification were quite different. to begin with, the slp algorithm was unable to complete execution with the e. coli, s. cerevisiae, and h. sapiens networks due to memory exhaustion. this also occurred for both the ms and ww algorithms with the h. sapiens network. therefore, at least for the hardware and software configurations used for these analyses, memory efficiency during extreme pathway identification was the most important factor for achieving successful computation. for the microbial networks, the maximum memory consumption of the ms algorithm was much less than that of the slp algorithm, and the memory consumption of the ww algorithm was less than that of the ms algorithm. the memory usage of both the ms and slp algorithms increased substantially with increasing network size, but in contrast, the memory usage of the ww algorithm changed little as the size of the microbial networks increased. similar trends were observed for time efficiency, as well. the observed performance differences of extreme pathway identification can best be explained by noting the reduction of network sizes achieved during the preprocessing phases of the ms and ww algorithms. the slp algorithm uses the entire network, whose numbers of reactions and metabolites are shown in table the ms algorithm uses sub-networks containing only reactions that participate in cycles, but the ww algorithm uses sub-networks containing only reactions that participate in cycles that are composed of more than two reactions. the reduction in size between the full network and the sub-network used by the ww algorithm is dramatic, spanning more than an order of magnitude for each of the microbial networks. for these networks, the majority of cycles are composed of only two reactions, allowing the ww algorithm to produce much smaller sub-networks than the ms algorithm. this greatly reduces the computational effort required of the slp algorithm, resulting in better performance. overall performance although the ww preprocessing step consumes more time and memory than ms preprocessing, the time and memory efficiency of identifying extreme pathways during the ww algorithm is dramatically better. consequently, the overall execution time of the ww algorithm is substantially less than the ms algorithm, and the memory consumption is also significantly reduced during the phase of the computation that is most memory-intensive and most susceptible to combinatorial explosion. caveats there are certain extreme cases where these performance differences will not persist. for example, if every reaction in a stoichiometric network participates in a cycle, the ms algorithm will fail to outperform the slp algorithm. in this situation, the maximum flux of each reaction will be unbounded, resulting in a "sub-network" that is exactly the same as the original. similarly, if every reaction in a stoichiometric network participates in cycles composed of more than two reactions, neither the ms nor ww algorithm will outperform the slp algorithm. if all the cycles in a stoichiometric network are composed of more than two reactions, the ww algorithm will fail to outperform the ms algorithm. if a reaction network does not contain any cycles, the ms algorithm will likely have a performance advantage over the ww algorithm, depending on implementation details. we note that these extreme scenarios are not realistic for genome-scale metabolic networks, the kinds of networks for which application of the ww algorithm would be most fruitful. if, finally, a network only contains cycles composed of two reactions, the ww algorithm will never make use of the slp algorithm, which eliminates the chance of combinatorial explosion and most likely provides further dramatic performance improvements over the ms algorithm. it should also be noted that the algorithmic performances described herein are dependent upon implementation details and the choice of underlying algorithms. other software and algorithms, for example, could be used to identify extreme pathways, which would certainly change the time and memory requirements of these computations. additionally, flux maximization was performed by both implementations of the ww and ms algorithms during the preprocessing phase. as mentioned above, replacing flux maximization with another technique, such as an infeasibility test, would also change the time and memory requirements of this portion of the algorithms.  the ww algorithm consistently achieves significant performance improvements over both the ms and slp algorithms for the microbial networks we examined. for these networks, the execution time and maximum memory consumption of the ww algorithm are both smaller by multiple factors. the scaling behavior of the ww algorithm as a function of network size is also preferable to both the ms and slp algorithms. due to combinatorial explosion during extreme pathway identification, however, all of the algorithms fail to identify the cycles within the human metabolic network. at this point in time, the ww algorithm appears to be the best choice for identifying steady state cycles in large, real-world stoichiometric networks, although additional algorithmic innovation is clearly desirable. 
unfortunately, our ability to identify cycles in stoichiometric networks, such as signal transduction and genome-scale metabolic networks, has been hampered by the computational complexity of the methods currently used. we describe a new algorithm for the identification of cycles in stoichiometric networks, and we compare its performance to two others by exhaustively identifying the cycles contained in the genome-scale metabolic networks of h. pylori, m. barkeri, e. coli, and s. cerevisiae. identifying cyclic pathways in chemical reaction networks is important, because such cycles may indicate in silico violation of energy conservation, or the existence of feedback in vivo. our algorithm can substantially decrease both the execution time and maximum memory usage in comparison to the two previous algorithms.
 identifying cyclic pathways in chemical reaction networks is important, because such cycles may indicate in silico violation of energy conservation, or the existence of feedback in vivo. unfortunately, our ability to identify cycles in stoichiometric networks, such as signal transduction and genome-scale metabolic networks, has been hampered by the computational complexity of the methods currently used.  we describe a new algorithm for the identification of cycles in stoichiometric networks, and we compare its performance to two others by exhaustively identifying the cycles contained in the genome-scale metabolic networks of h. pylori, m. barkeri, e. coli, and s. cerevisiae. our algorithm can substantially decrease both the execution time and maximum memory usage in comparison to the two previous algorithms.  the algorithm we describe improves our ability to study large, real-world, biochemical reaction networks, although additional methodological improvements are desirable. 