Computing irreversible minimal cut sets in genome-scale metabolic networks via flux cone projection

Speeding up the core algorithm for the dual calculation of minimal cut sets in large metabolic networks

Background

The concept of minimal cut sets (MCS) has become an important mathematical framework for analyzing and (re)designing metabolic networks. However, the calculation of MCS in genome-scale metabolic models is a complex computational problem. The development of duality-based algorithms in the last years allowed the enumeration of thousands of MCS in genome-scale networks by solving mixed-integer linear problems (MILP). A recent advancement in this field was the introduction of the MCS² approach. In contrast to the Farkas-lemma-based dual system used in earlier studies, the MCS² approach employs a more condensed representation of the dual system based on the nullspace of the stoichiometric matrix, which, due to its reduced dimension, holds promise to further enhance MCS computations.

Results

In this work, we introduce several new variants and modifications of duality-based MCS algorithms and benchmark their effects on the overall performance. As one major result, we generalize the original MCS² approach (which was limited to blocking the operation of certain target reactions) to the most general case of MCS computations with arbitrary target and desired regions. Building upon these developments, we introduce a new MILP variant which allows maximal flexibility in the formulation of MCS problems and fully leverages the reduced size of the nullspace-based dual system. With a comprehensive set of benchmarks, we show that the MILP with the nullspace-based dual system outperforms the MILP with the Farkas-lemma-based dual system speeding up MCS computation with an averaged factor of approximately 2.5. We furthermore present several simplifications in the formulation of constraints, mainly related to binary variables, which further enhance the performance of MCS-related MILP. However, the benchmarks also reveal that some highly condensed formulations of constraints, especially on reversible reactions, may lead to worse behavior when compared to variants with a larger number of (more explicit) constraints and involved variables.

Conclusions

Our results further enhance the algorithmic toolbox for MCS calculations and are of general importance for theoretical developments as well as for practical applications of the MCS framework.

Boosting the extraction of elementary flux modes in genome-scale metabolic networks using the linear programming approach

MOTIVATION

Elementary flux modes (EFMs) are a key tool for analyzing genome-scale metabolic networks, and several methods have been proposed to compute them. Among them, those based on solving linear programming (LP) problems are known to be very efficient if the main interest lies in computing large enough sets of EFMs.

RESULTS

Here, we propose a new method called EFM-Ta that boosts the efficiency rate by analyzing the information provided by the LP solver. We base our method on a further study of the final tableau of the simplex method. By performing additional elementary steps and avoiding trivial solutions consisting of two cycles, we obtain many more EFMs for each LP problem posed, improving the efficiency rate of previously proposed methods by more than one order of magnitude.

AVAILABILITY AND IMPLEMENTATION

Software is freely available at https://github.com/biogacop/Boost_LP_EFM.

CONTACT

fguil@um.es.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

An extended and generalized framework for the calculation of metabolic intervention strategies based on minimal cut sets

The concept of minimal cut sets (MCS) provides a flexible framework for analyzing properties of metabolic networks and for computing metabolic intervention strategies. In particular, it has been used to support the targeted design of microbial strains for bio-based production processes. Herein we present a number of major extensions that generalize the existing MCS approach and broaden its scope for applications in metabolic engineering. We first introduce a modified approach to integrate gene-protein-reaction associations (GPR) in the metabolic network structure for the computation of gene-based intervention strategies. In particular, we present a set of novel compression rules for GPR associations, which effectively speedup the computation of gene-based MCS by a factor of up to one order of magnitude. These rules are not specific for MCS and as well applicable to other computational strain design methods. Second, we enhance the MCS framework by allowing the definition of multiple target (undesired) and multiple protected (desired) regions. This enables precise tailoring of the metabolic solution space of the designed strain with unlimited flexibility. Together with further generalizations such as individual cost factors for each intervention, direct combinations of reaction/gene deletions and additions as well as the possibility to search for substrate co-feeding strategies, the scope of the MCS framework could be broadly extended. We demonstrate the applicability and performance benefits of the described developments by computing (gene-based) Escherichia coli strain designs for the bio-based production of 2,3-butanediol, a chemical, that has recently received much attention in the field of metabolic engineering. With our extended framework, we could identify promising strain designs that were formerly unpredictable, including those based on substrate co-feeding.

MCS2: minimal coordinated supports for fast enumeration of minimal cut sets in metabolic networks

Motivation

Constraint-based modeling of metabolic networks helps researchers gain insight into the metabolic processes of many organisms, both prokaryotic and eukaryotic. Minimal cut sets (MCSs) are minimal sets of reactions whose inhibition blocks a target reaction in a metabolic network. Most approaches for finding the MCSs in constrained-based models require, either as an intermediate step or as a byproduct of the calculation, the computation of the set of elementary flux modes (EFMs), a convex basis for the valid flux vectors in the network. Recently, Ballerstein et al. proposed a method for computing the MCSs of a network without first computing its EFMs, by creating a dual network whose EFMs are a superset of the MCSs of the original network. However, their dual network is always larger than the original network and depends on the target reaction. Here we propose the construction of a different dual network, which is typically smaller than the original network and is independent of the target reaction, for the same purpose. We prove the correctness of our approach, minimal coordinated support (MCS²), and describe how it can be modified to compute the few smallest MCSs for a given target reaction.

Results

We compare MCS² to the method of Ballerstein et al. and two other existing methods. We show that MCS² succeeds in calculating the full set of MCSs in many models where other approaches cannot finish within a reasonable amount of time. Thus, in addition to its theoretical novelty, our approach provides a practical advantage over existing methods.

Availability and implementation

MCS² is freely available at https://github.com/RezaMash/MCS under the GNU 3.0 license.

Supplementary information

Supplementary data are available at Bioinformatics online.

Finding MEMo: minimum sets of elementary flux modes

Metabolic network reconstructions are widely used in computational systems biology for in silico studies of cellular metabolism. A common approach to analyse these models are elementary flux modes (EFMs), which correspond to minimal functional units in the network. Already for medium-sized networks, it is often impossible to compute the set of all EFMs, due to their huge number. From a practical point of view, this might also not be necessary because a subset of EFMs may already be sufficient to answer relevant biological questions. In this article, we study MEMos or minimum sets of EFMs that can generate all possible steady-state behaviours of a metabolic network. The number of EFMs in a MEMo may be by several orders of magnitude smaller than the total number of EFMs. Using MEMos, we can compute generating sets of EFMs in metabolic networks where the whole set of EFMs is too large to be enumerated.