Minimal cut sets (MCSs) have emerged as an important branch of constraint-based metabolic modeling, offering a versatile framework for analyzing and engineering metabolic networks. Over the past two decades, MCSs have evolved from a theoretical concept into a powerful tool for identifying tailored metabolic intervention strategies and studying robustness and failure modes of metabolic networks. Successful (experimental) applications range from designing highly efficient microbial cell factories to targeting cancer cell metabolism. This review highlights key conceptual and algorithmic advancements that have transformed MCSs into a flexible methodology applicable to metabolic models of any size. It also provides a comprehensive overview of their applications and concludes with a perspective on future research directions. The review aims to equip both newcomers and experts with the knowledge needed to effectively leverage MCSs for metabolic network analysis and design, therapeutic targeting, and beyond.

MOTIVATION: Flux balance analysis (FBA) is widely recognized as an important method for studying metabolic networks. When incorporating flux measurements of certain reactions into an FBA problem, it is possible that the underlying linear program may become infeasible, e.g. due to measurement or modeling inaccuracies. Furthermore, while the biomass reaction is of central importance in FBA models, its stoichiometry is often a rough estimate and a source of high uncertainty. RESULTS: In this work, we present a method that allows modifications to the biomass reaction stoichiometry as a means to (i) render the FBA problem feasible and (ii) improve the accuracy of the model by corrections in the biomass composition. Optionally, the adjustment of the biomass composition can be used in conjunction with a previously introduced approach for balancing inconsistent fluxes to obtain a feasible FBA system. We demonstrate the value of our approach by analyzing realistic flux measurements of E.coli. In particular, we find that the growth-associated maintenance (GAM) demand of ATP, which is typically integrated with the biomass reaction, is likely overestimated in recent genome-scale models, at least for certain growth conditions. In light of these findings, we discuss issues related to the determination and inclusion of GAM values in constraint-based models. Overall, our method can uncover potential errors and suggest adjustments in the assumed biomass composition in FBA models based on inconsistencies between the model and measured fluxes. AVAILABILITY AND IMPLEMENTATION: The developed method has been implemented in our software tool CNApy available from https://github.com/cnapy-org/CNApy.

SUMMARY: Various constraint-based optimization approaches have been developed for the computational analysis and design of metabolic networks. Herein, we present StrainDesign, a comprehensive Python package that builds upon the COBRApy toolbox and integrates the most popular metabolic design algorithms, including nested strain optimization methods such as OptKnock, RobustKnock and OptCouple as well as the more general minimal cut sets approach. The optimization approaches are embedded in individual modules, which can also be combined for setting up more elaborate strain design problems. Advanced features, such as the efficient integration of GPR rules and the possibility to consider gene and reaction additions or regulatory interventions, have been generalized and are available for all modules. The package uses state-of-the-art preprocessing methods, supports multiple solvers and provides a number of enhanced tools for analyzing computed intervention strategies including 2D and 3D plots of user-selected metabolic fluxes or yields. Furthermore, a user-friendly interface for the StrainDesign package has been implemented in the GUI-based metabolic modeling software CNApy. StrainDesign provides thus a unique and rich framework for computational strain design in Python, uniting many algorithmic developments in the field and allowing modular extension in the future. AVAILABILITY AND IMPLEMENTATION: The StrainDesign package can be retrieved from PyPi, Anaconda and GitHub (https://github.com/klamt-lab/straindesign) and is also part of the latest CNApy package.

SUMMARY: Constraint-based reconstruction and analysis (COBRA) is a widely used modeling framework for analyzing and designing metabolic networks. Here, we present CNApy, an open-source cross-platform desktop application written in Python, which offers a state-of-the-art graphical front-end for the intuitive analysis of metabolic networks with COBRA methods. While the basic look-and-feel of CNApy is similar to the user interface of the MATLAB toolbox CellNetAnalyzer, it provides various enhanced features by using components of the powerful Qt library. CNApy supports a number of standard and advanced COBRA techniques and further functionalities can be easily embedded in its GUI facilitating modular extension in the future. AVAILABILITY AND IMPLEMENTATION: CNApy can be installed via conda and its source code is freely available at https://github.com/cnapy-org/CNApy under the Apache 2 license.

Abstract 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 MCS2approach. In contrast to the Farkas-lemma-based dual system used in earlier studies, the MCS2approach 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 MCS2approach (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.

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.

Constraint-based modeling techniques have become a standard tool for the in silico analysis of metabolic networks. To further improve their accuracy, recent methodological developments focused on integration of thermodynamic information in metabolic models to assess the feasibility of flux distributions by thermodynamic driving forces. Here we present OptMDFpathway, a method that extends the recently proposed framework of Max-min Driving Force (MDF) for thermodynamic pathway analysis. Given a metabolic network model, OptMDFpathway identifies both the optimal MDF for a desired phenotypic behavior as well as the respective pathway itself that supports the optimal driving force. OptMDFpathway is formulated as a mixed-integer linear program and is applicable to genome-scale metabolic networks. As an important theoretical result, we also show that there exists always at least one elementary mode in the network that reaches the maximal MDF. We employed our new approach to systematically identify all substrate-product combinations in Escherichia coli where product synthesis allows for concomitant net CO2 assimilation via thermodynamically feasible pathways. Although biomass synthesis cannot be coupled to net CO2 fixation in E. coli we found that as many as 145 of the 949 cytosolic carbon metabolites contained in the genome-scale model iJO1366 enable net CO2 incorporation along thermodynamically feasible pathways with glycerol as substrate and 34 with glucose. The most promising products in terms of carbon assimilation yield and thermodynamic driving forces are orotate, aspartate and the C4-metabolites of the tricarboxylic acid cycle. We also identified thermodynamic bottlenecks frequently limiting the maximal driving force of the CO2-fixing pathways. Our results indicate that heterotrophic organisms like E. coli hold a possibly underestimated potential for CO2 assimilation which may complement existing biotechnological approaches for capturing CO2. Furthermore, we envision that the developed OptMDFpathway approach can be used for many other applications within the framework of constrained-based modeling and for rational design of metabolic networks.

MOTIVATION: Stoichiometric and constraint-based methods of computational strain design have become an important tool for rational metabolic engineering. One of those relies on the concept of constrained minimal cut sets (cMCSs). However, as most other techniques, cMCSs may consider only reaction (or gene) knockouts to achieve a desired phenotype. RESULTS: We generalize the cMCSs approach to constrained regulatory MCSs (cRegMCSs), where up/downregulation of reaction rates can be combined along with reaction deletions. We show that flux up/downregulations can virtually be treated as cuts allowing their direct integration into the algorithmic framework of cMCSs. Because of vastly enlarged search spaces in genome-scale networks, we developed strategies to (optionally) preselect suitable candidates for flux regulation and novel algorithmic techniques to further enhance efficiency and speed of cMCSs calculation. We illustrate the cRegMCSs approach by a simple example network and apply it then by identifying strain designs for ethanol production in a genome-scale metabolic model of Escherichia coli. The results clearly show that cRegMCSs combining reaction deletions and flux regulations provide a much larger number of suitable strain designs, many of which are significantly smaller relative to cMCSs involving only knockouts. Furthermore, with cRegMCSs, one may also enable the fine tuning of desired behaviours in a narrower range. The new cRegMCSs approach may thus accelerate the implementation of model-based strain designs for the bio-based production of fuels and chemicals. AVAILABILITY AND IMPLEMENTATION: MATLAB code and the examples can be downloaded at http://www.mpi-magdeburg.mpg.de/projects/cna/etcdownloads.html. CONTACT: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

One ultimate goal of metabolic network modeling is the rational redesign of biochemical networks to optimize the production of certain compounds by cellular systems. Although several constraint-based optimization techniques have been developed for this purpose, methods for systematic enumeration of intervention strategies in genome-scale metabolic networks are still lacking. In principle, Minimal Cut Sets (MCSs; inclusion-minimal combinations of reaction or gene deletions that lead to the fulfilment of a given intervention goal) provide an exhaustive enumeration approach. However, their disadvantage is the combinatorial explosion in larger networks and the requirement to compute first the elementary modes (EMs) which itself is impractical in genome-scale networks. We present MCSEnumerator, a new method for effective enumeration of the smallest MCSs (with fewest interventions) in genome-scale metabolic network models. For this we combine two approaches, namely (i) the mapping of MCSs to EMs in a dual network, and (ii) a modified algorithm by which shortest EMs can be effectively determined in large networks. In this way, we can identify the smallest MCSs by calculating the shortest EMs in the dual network. Realistic application examples demonstrate that our algorithm is able to list thousands of the most efficient intervention strategies in genome-scale networks for various intervention problems. For instance, for the first time we could enumerate all synthetic lethals in E.coli with combinations of up to 5 reactions. We also applied the new algorithm exemplarily to compute strain designs for growth-coupled synthesis of different products (ethanol, fumarate, serine) by E.coli. We found numerous new engineering strategies partially requiring less knockouts and guaranteeing higher product yields (even without the assumption of optimal growth) than reported previously. The strength of the presented approach is that smallest intervention strategies can be quickly calculated and screened with neither network size nor the number of required interventions posing major challenges.

MOTIVATION: Elementary modes (EMs) and minimal cut sets (MCSs) provide important techniques for metabolic network modeling. Whereas EMs describe minimal subnetworks that can function in steady state, MCSs are sets of reactions whose removal will disable certain network functions. Effective algorithms were developed for EM computation while calculation of MCSs is typically addressed by indirect methods requiring the computation of EMs as initial step. RESULTS: In this contribution, we provide a method that determines MCSs directly without calculating the EMs. We introduce a duality framework for metabolic networks where the enumeration of MCSs in the original network is reduced to identifying the EMs in a dual network. As a further extension, we propose a generalization of MCSs in metabolic networks by allowing the combination of inhomogeneous constraints on reaction rates. This framework provides a promising tool to open the concept of EMs and MCSs to a wider class of applications. CONTACT: [email protected]; [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Interaction graphs (signed directed graphs) provide an important qualitative modeling approach for Systems Biology. They enable the analysis of causal relationships in cellular networks and can even be useful for predicting qualitative aspects of systems dynamics. Fundamental issues in the analysis of interaction graphs are the enumeration of paths and cycles (feedback loops) and the calculation of shortest positive/negative paths. These computational problems have been discussed only to a minor extent in the context of Systems Biology and in particular the shortest signed paths problem requires algorithmic developments. RESULTS: We first review algorithms for the enumeration of paths and cycles and show that these algorithms are superior to a recently proposed enumeration approach based on elementary-modes computation. The main part of this work deals with the computation of shortest positive/negative paths, an NP-complete problem for which only very few algorithms are described in the literature. We propose extensions and several new algorithm variants for computing either exact results or approximations. Benchmarks with various concrete biological networks show that exact results can sometimes be obtained in networks with several hundred nodes. A class of even larger graphs can still be treated exactly by a new algorithm combining exhaustive and simple search strategies. For graphs, where the computation of exact solutions becomes time-consuming or infeasible, we devised an approximative algorithm with polynomial complexity. Strikingly, in realistic networks (where a comparison with exact results was possible) this algorithm delivered results that are very close or equal to the exact values. This phenomenon can probably be attributed to the particular topology of cellular signaling and regulatory networks which contain a relatively low number of negative feedback loops. CONCLUSION: The calculation of shortest positive/negative paths and cycles in interaction graphs is an important method for network analysis in Systems Biology. This contribution draws the attention of the community to this important computational problem and provides a number of new algorithms, partially specifically tailored for biological interaction graphs. All algorithms have been implemented in the CellNetAnalyzer framework which can be downloaded for academic use at http://www.mpi-magdeburg.mpg.de/projects/cna/cna.html.

SUMMARY: Elementary modes analysis is a powerful tool in the constraint-based modeling of metabolic networks. In recent years, new approaches to calculating elementary modes in biochemical reaction networks have been developed. As a consequence, the program Metatool, which is one of the first programs dedicated to this purpose, has been reimplemented in order to make use of these new approaches. The performance of Metatool has been significantly increased and the new version 5.0 can now be run inside the GNU octave or Matlab environments to allow more flexible usage and integration with other tools. AVAILABILITY: The script files and compiled shared libraries can be downloaded from the Metatool website at http://pinguin.biologie.uni-jena.de/bioinformatik/networks/index.html. Metatool consists of script files (m-files) for GNU octave as well as Matlab and shared libraries. The scripts are licensed under the GNU Public License and the use of the shared libraries is free for academic users and testing purposes. Commercial use of Metatool requires a special contract.

BACKGROUND: A number of algorithms for steady state analysis of metabolic networks have been developed over the years. Of these, Elementary Mode Analysis (EMA) has proven especially useful. Despite its low user-friendliness, METATOOL as a reliable high-performance implementation of the algorithm has been the instrument of choice up to now. As reported here, the analysis of metabolic networks has been improved by an editor and analyzer of metabolic flux modes. Analysis routines for expression levels and the most central, well connected metabolites and their metabolic connections are of particular interest. RESULTS: YANA features a platform-independent, dedicated toolbox for metabolic networks with a graphical user interface to calculate (integrating METATOOL), edit (including support for the SBML format), visualize, centralize, and compare elementary flux modes. Further, YANA calculates expected flux distributions for a given Elementary Mode (EM) activity pattern and vice versa. Moreover, a dissection algorithm, a centralization algorithm, and an average diameter routine can be used to simplify and analyze complex networks. Proteomics or gene expression data give a rough indication of some individual enzyme activities, whereas the complete flux distribution in the network is often not known. As such data are noisy, YANA features a fast evolutionary algorithm (EA) for the prediction of EM activities with minimum error, including alerts for inconsistent experimental data. We offer the possibility to include further known constraints (e.g. growth constraints) in the EA calculation process. The redox metabolism around glutathione reductase serves as an illustration example. All software and documentation are available for download at http://yana.bioapps.biozentrum.uni-wuerzburg.de. CONCLUSION: A graphical toolbox and an editor for METATOOL as well as a series of additional routines for metabolic network analyses constitute a new user-friendly software for such efforts.