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

Minimal cut sets in metabolic networks: from conceptual foundations to applications in metabolic engineering and biomedicine

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.

Algorithms for evaluation of minimal cut sets

OBJECTIVE

We propose a way to enhance the evaluation of minimal cut sets (MCSs) in biological systems modeled by Petri nets, by providing criteria and methodology for determining their optimality in disabling specific processes without affecting critical system components.

METHODS

This study concerns Petri nets to model biological systems and utilizes two primary approaches for MCS evaluation. First is the analyzing impact on t-invariants to identify structural dependencies. Second is assessing the impact on potentially starved transitions caused by the inactivity of specific MCSs. This approach deal with net dynamics. These methodologies aim to offer practical tools for assessing the quality and effectiveness of MCSs.

RESULTS

The proposed methodologies were applied to two case studies. In the first case, a cholesterol metabolism network was analyzed to investigate how local inflammation and oxidative stress, in conjunction with cholesterol imbalances, influence the progression of atherosclerosis. The MCSs were ranked, with the top sets presented, focusing on those that disabled the fewest number of t-invariants. In the second case, a carbohydrate metabolism disorder model was examined to understand its impact on atherosclerosis progression. The analysis aimed to identify MCSs that could inhibit the atherosclerosis process by targeting specific transitions. Both studies utilized the Holmes software for calculations, demonstrating the effectiveness of the proposed evaluation methodologies in ranking MCSs for practical biological applications.

CONCLUSION

The algorithms proposed in this paper offer an analytical approach for evaluating the quality of MCSs in biological systems. By providing criteria for MCS optimality, these approaches have potential to enhance the utility of MCS analysis in systems biology, aiding in the understanding and manipulation of complex biological networks. Algorithm are implemented within Holmes software, an open-source project available at https://github.com/bszawulak/HolmesPN.

Rapid-SL identifies synthetic lethal sets with an arbitrary cardinality

The multidrug resistance of numerous pathogenic microorganisms is a serious challenge that raises global healthcare concerns. Multi-target medications and combinatorial therapeutics are much more effective than single-target drugs due to their synergistic impact on the systematic activities of microorganisms. Designing efficient combinatorial therapeutics can benefit from identification of synthetic lethals (SLs). An SL is a set of non-essential targets (i.e., reactions or genes) that prevent the proliferation of a microorganism when they are "knocked out" simultaneously. To facilitate the identification of SLs, we introduce Rapid-SL, a new multimodal implementation of the Fast-SL method, using the depth-first search algorithm. The advantages of Rapid-SL over Fast-SL include: (a) the enumeration of all SLs that have an arbitrary cardinality, (b) a shorter runtime due to search space reduction, (c) embarrassingly parallel computations, and (d) the targeted identification of SLs. Targeted identification is important because the enumeration of higher order SLs demands the examination of too many reaction sets. Accordingly, we present specific applications of Rapid-SL for the efficient targeted identification of SLs. In particular, we found up to 67% of all quadruple SLs by investigating about 1% of the search space. Furthermore, 307 sextuples, 476 septuples, and over 9000 octuples are found for Escherichia coli genome-scale model, iAF1260.

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.

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.