Enumeration of minimal stoichiometric precursor sets in metabolic networks

Abstract

Background: What an organism needs at least from its environment to produce a set of metabolites, e.g. target(s) of interest and/or biomass, has been called a minimal precursor set. Early approaches to enumerate all minimal precursor sets took into account only the topology of the metabolic network (topological precursor sets). Due to cycles and the stoichiometric values of the reactions, it is often not possible to produce the target(s) from a topological precursor set in the sense that there is no feasible flux. Although considering the stoichiometry makes the problem harder, it enables to obtain biologically reasonable precursor sets that we call stoichiometric. Recently a method to enumerate all minimal stoichiometric precursor sets was proposed in the literature. The relationship between topological and stoichiometric precursor sets had however not yet been studied.

Results: Such relationship between topological and stoichiometric precursor sets is highlighted. We also present two algorithms that enumerate all minimal stoichiometric precursor sets. The first one is of theoretical interest only and is based on the above mentioned relationship. The second approach solves a series of mixed integer linear programming problems. We compared the computed minimal precursor sets to experimentally obtained growth media of several Escherichia coli strains using genome-scale metabolic networks.

Conclusions: The results show that the second approach efficiently enumerates minimal precursor sets taking stoichiometry into account, and allows for broad in silico studies of strains or species interactions that may help to understand e.g. pathotype and niche-specific metabolic capabilities. sasita is written in Java, uses cplex as LP solver and can be downloaded together with all networks and input files used in this paper at http://www.sasita.gforge.inria.fr.

Keywords: Metabolic network; Minimal precursor sets; Mixed integer linear programming.

Fig. 1

Network with one source p and one target t illustrating the difference between the two models used by Eker et al. [8], and the limitation of the machinery-duplicating model. The source p is a precursor set for the production of the target if the steady-state model is assumed. In this toy example, the target can not be produced following the machinery-duplicating model

Fig. 2

Illustration of facts 2–4. The stoichiometric values are all equal to one. There are two minimal TPSs: $\{p1\}$ (obtained from the topological factory $\{r_1,r_3,r_4\}$), and $\{p3\}$ (obtained from the topological factory $\{r_7,r_6,r_5\}$). The source p2 does not take part of a minimal topological factory because its consumption involves the consumption of the source p3, which forms already a minimal TPS. There are two minimal SPSs: $\{p1\}$ (obtained from the stoichiometric factory $\{r_1,r_2,r_3,r_4\}$), and $\{p2,p3\}$ (obtained from the stoichiometric factory $\{r_8\}$)

Fig. 3

a A network with $\mathcal{R}=\{r_t,r_a,r_b,r_1,\cdots ,r_n\}$. Reaction $r_i$ with $i=2,\cdots ,n$ consumes $p_i$ and produces compound c. $\mathcal{T}=\{t\}$, $\mathcal{X}=\{p_1,\cdots ,p_n\}$. All stoichiometric values are equal to one. There is one minimal $SPS$ ($\{p_1\}$) and n minimal topological factories in $\mathit{\psi }(\mathcal{N})$ . One contains only $\mathit{\psi }(r_1)$. The other minimal topological factories contain each $\{\mathit{\psi }(r_t),\mathit{\psi }(r_a),\mathit{\psi }(r_b)\}$ and one of the reactions in $\{\mathit{\psi }(r_2),\cdots ,\mathit{\psi }(r_n)\}$, respectively. b In this network, the set of compounds is given by $\mathcal{C}=\{a,b,t,c_1,\cdots ,c_n,p_1,\cdots ,p_n\}$. The compounds $p_1,\cdots ,p_n$ are the sources and t is the target. The stoichiometric values are equal to 1 if not stated otherwise. Beside the reactions $r_{a_1}:a\to t$ and $r_{a_2}:a\to b$, there is the reaction $r^{\prime }$ that consumes $n-1$ b and produces $\{c_1,\cdots ,c_n\}$ (1 each). Furthermore, there are n reactions with $\mathit{S}ubs(r_i)=\{c_i,p_i\}$ and $\mathit{P}rod(r_i)=\{a\}$, with $i=1,\cdots ,n$. The dots in the Figure illustrate the products $c_2,\cdots ,c_{n-1}$ of $r^{\prime }$ that are not shown for simplicity. The reactions $r_2,\cdots ,r_{n-1}$ are not shown for the same reason. There are n minimal topological factories in $\mathit{\psi }(\mathcal{N})$, each containing the reactions $\{\mathit{\psi }(r_{a_1}),\mathit{\psi }(r_{a_2}),\mathit{\psi }(r^{\prime })\}$ and one of the many-to-one reactions of $\{\mathit{\psi }(r_1),\cdots ,\mathit{\psi }(r_n)\}$, respectively. The only minimal $SPS$ contains all sources