An efficient sampling method for non-convex
thermodynamic solution space of genome-scale networks
F. Yang
∗
and F. Qi
Zhejiang University
(Dated: February 22, 2007)
Constraint-based approaches, such as flux balance analysis (FBA) and energy balance analy-
sis(EBA), are widely applied to study a variety of metabolic networks. While the convex mass-
balance solution space has b een rigourously characterized, the nonconvex thermodynamically fea-
sible solution space has not been characterized yet, especially for large-scale biochemical networks.
Therefore, developing an efficient sampling technique to characterize the physicochemically feasible
solution space is critical. Here we present an efficient method to uniformly sample the nonconvex
thermodynamically feasible solution space. By studying the characteristics of sampled flux distri-
butions, the thermodynamic feasibility and directionality of some key reactions are revealed. The
developed methodology can be used to revise currently available metabolic networks, and systemati-
cally determine feasible flux directions which satisfy both mass-balance and thermodynamic-balance
constraints.
Keywords: Constraint-based, thermodynamics, nonconvex, sampling, metabolic networks, directionality
I. INTRODUCTION:
A large number of closely related techniques that ap-
ply knowledge of the stoichiometric structure of reaction
networks to probe system’s function are available [1].
These techniques apply constraints on feasible reaction
fluxes that are imposed by steady-state mass conserva-
tion and thermodynamic constraints defining allowable
reaction directions. While both mass-conservation con-
straints and thermodynamic (T) constraints arise from
the stoichiometry of a given network [2–5], usually only
the linear mass-conservation constraints are rigorously
applied [6]. The implications of imposing thermody-
namic constraints on biochemical networks have not been
clearly defined yet, especially for large-scale networks.
The difficulty of applying thermodynamic constraints
lies on the fact that the defined solution space is im-
plicitly nonlinear, which leads to its nonconvex char-
acteristic. Specifically, the intersection of the steady
state mass balance and thermodynamic solution space
is not a convex space; combing two elementary modes
is not guaranteed to generate a T-feasible flux distribu-
tion [7]. Although some studies have performed ther-
modynamic analyses on large-scale networks, they typi-
cally accepted the corresponding reconstructed networks
to be intact [4, 5], or slightly modified them based on
thermodynamics-based heuristic rules [8]. In fact, the
procedure for determining feasible reaction directions in
these networks is less concrete and arbitrary to some de-
gree. Typically, a subset of the reactions in a model are
assigned as irreversible and the feasible directions are as-
signed based on information in pathway databases [9].
Such assignments ignore the fact that all reactions are in
principle reversible.
∗
Electronic address: fyangusa@gmail.com
For small-scale networks for which the computation
of complete modes is possible, one implication of T-
constraints has been identified, that is, the flux direc-
tions can be possibly computed based on the given spec-
ification of the directions of a subset of network fluxes
(mostly exchange fluxes) [7]. However, this algorithm
is based on the NP-complete computation of entire ele-
mentary modes. For a genome-scale network, completely
enumerating all modes is not realistic. Therefore, the
characteristics of the thermodynamic solution space of
genome-scale networks are unknown so far, and useful
techniques to sample the T-feasible solution space for
genome-scale networks are yet to be introduced.
Here, a genome-scale algorithm for characterizing the
physicochemically feasible solution space is introduced
and applied to the biochemical network models of Es-
cherichia coli. It is shown that the feasibilities and the
directions of some key reactions can be ab initio deter-
mined, and the resulting biochemical network could make
more accurate flux distribution predictions than using
flux balance analysis only.
II. MATHEMATICAL BACKGROUND:
For a given network, the mass-conservation constraints
can be mathematically presented as follows,
X
j
S
ij
· J
j
= 0, and
~
J obeys Ψ, (1)
where
~
J is a flux vector, Ψ represents boundary condi-
tions, and S
ij
is the stoichiometric coefficient of metabo-
lite i and reaction j. The space defined by Eq. 1
represents a linearly constrained, convex solution space
[6]. The nonlinear thermodynamic constraints, however,
arise from the fact that there must exist a thermody-
namic driving force for any mass-balanced set of reaction
fluxes. Mathematically speaking, for a flux vector
~
J to be
http://www.paper.edu.cn