Computing Thermodynamically Consistent Elementary Flux Modes with Answer Set Programming

Abstract

Elementary Flux Modes (EFM) allow the description of the minimal sets of reactions in a metabolic network under steady-state conditions, representing unique and feasible pathways. They fully characterize the solution space but a combinatorial explosion prevents their calculation when the network is large. Furthermore, it is not necessary to calculate all of them, as many of them are not biologically relevant.

Therefore, the software aspefm, which combines the use of Answer Set Programming and Linear Programming, proposes to integrate different types of constraints in the EFM computation such as equilibrium constants, Boolean regulatory rules, growth yields and growth medium. The addition of constraints makes it possible to cut off research pathways that lead to non-relevant EFMs. The computation of the EFMs of interest significantly reduces the computational time and saves space. In this article, we have added thermodynamic constraints in terms of the Gibbs energy of reactions, which constrain metabolite concentrations within a chosen interval. This constraint is added as a theory propagator and it reduces the enumeration during the computation. We applied our tool to the central carbon metabolism of E. coli and showed that the Gibbs energy constraints suppress a large number of non-relevant EFMs.

A Appendix

Fig. 2.

Evaluation of aspefm computation times for E. coli depending on percentages around the selected intervals; 1) aspefm with DGChecker off: aspefm times for computing E.coli model EFMs without using extension DeltaGChecker; 2) aspefm + DGChecker: aspefm times for computing E. coli model EFMs using the DeltaGChecker extension, for each percentage around the fixed concentration value; 3) aspefm alone: for each percentage, portion of time spent computing aspefm solutions, without checking thermodynamics; 4) DGChecker alone: for each percentage, portion of time spent checking thermodynamics in the DeltaGChecker extension.

1.1 A.1 Computation Times on E.coli

The thermodynamic extension makes it possible to reduce the number of EFMs of interest, and therefore the post-processing search, but it’s interesting to look at and compare what the extension can bring to processing. The extension reduces the number of paths used to search for EFMs, and therefore saves time on paths that we know to be thermodynamically infeasible. On the other hand, the extension will waste time on path traversal, because for each EFM support tested, it will be necessary to check whether the support has a concentration set solution that validates the thermodynamics, which implies running the CPLEX solver. So, for the extension to be cost-effective in terms of computation time, the absence of some non-thermodynamically feasible EFM paths would have to be beneficial in terms of the computation time added to test whether each partial support has a thermodynamically feasible solution.

This figure shows the same percentages used in the previous study (Fig. 2). It was seen that the lower the percentage, the more the extension restricted the number of EFMs of interest, so that the extension must have had an impact on the paths taken by the EFMs. As the percentage increased, the number of EFMs of interest increased, approaching the number found by aspefm without the addition of the extension, due to the fact that the thermodynamic constraints were not strong enough. We note that in the case of the E.coli model, computation times of aspefm oscillates between 25.6 and 28.4 s while not increasing with the percentage as would be expected; time within and outside the extension remains approximately constant. Surprisingly, filtering out more solutions had no effect on the computation time. This result might be explained by the fact that the network is not large enough, i.e. the time saved by not traversing certain paths is not visible at this scale. Overall, when removing the times taken by the extension, we find that the differences in time are almost all attributable to the extension, with a time difference of around $\sim$ 2 s (on average 17.51 against 15.56).

This is a promising result, and we hope that computation times for our filtering procedure will be able to scale to larger networks.