Speeding up the core algorithm for the dual calculation of minimal cut sets in large 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.

Cell factory design with advanced metabolic modelling empowered by artificial intelligence

Advances in synthetic biology and artificial intelligence (AI) have provided new opportunities for modern biotechnology. High-performance cell factories, the backbone of industrial biotechnology, are ultimately responsible for determining whether a bio-based product succeeds or fails in the fierce competition with petroleum-based products. To date, one of the greatest challenges in synthetic biology is the creation of high-performance cell factories in a consistent and efficient manner. As so-called white-box models, numerous metabolic network models have been developed and used in computational strain design. Moreover, great progress has been made in AI-powered strain engineering in recent years. Both approaches have advantages and disadvantages. Therefore, the deep integration of AI with metabolic models is crucial for the construction of superior cell factories with higher titres, yields and production rates. The detailed applications of the latest advanced metabolic models and AI in computational strain design are summarized in this review. Additionally, approaches for the deep integration of AI and metabolic models are discussed. It is anticipated that advanced mechanistic metabolic models powered by AI will pave the way for the efficient construction of powerful industrial chassis strains in the coming years.

Convex Representation of Metabolic Networks with Michaelis-Menten Kinetics

Polyhedral models of metabolic networks are computationally tractable and can predict some cellular functions. A longstanding challenge is incorporating metabolites without losing tractability. In this paper, we do so using a new second-order cone representation of the Michaelis-Menten kinetics. The resulting model consists of linear stoichiometric constraints alongside second-order cone constraints that couple the reaction fluxes to metabolite concentrations. We formulate several new problems around this model: conic flux balance analysis, which augments flux balance analysis with metabolite concentrations; dynamic conic flux balance analysis; and finding minimal cut sets of networks with both reactions and metabolites. Solving these problems yields information about both fluxes and metabolite concentrations. They are second-order cone or mixed-integer second-order cone programs, which, while not as tractable as their linear counterparts, can nonetheless be solved at practical scales using existing software.

FastKnock: an efficient next-generation approach to identify all knockout strategies for strain optimization

Overproduction of desired native or nonnative biochemical(s) in (micro)organisms can be achieved through metabolic engineering. Appropriate rewiring of cell metabolism is performed by making rational changes such as insertion, up-/down-regulation and knockout of genes and consequently metabolic reactions. Finding appropriate targets (including proper sets of reactions to be knocked out) for metabolic engineering to design optimal production strains has been the goal of a number of computational algorithms. We developed FastKnock, an efficient next-generation algorithm for identifying all possible knockout strategies (with a predefined maximum number of reaction deletions) for the growth-coupled overproduction of biochemical(s) of interest. We achieve this by developing a special depth-first traversal algorithm that allows us to prune the search space significantly. This leads to a drastic reduction in execution time. We evaluate the performance of the FastKnock algorithm using various Escherichia coli genome-scale metabolic models in different conditions (minimal and rich mediums) for the overproduction of a number of desired metabolites. FastKnock efficiently prunes the search space to less than 0.2% for quadruple- and 0.02% for quintuple-reaction knockouts. Compared to the classic approaches such as OptKnock and the state-of-the-art techniques such as MCSEnumerator methods, FastKnock found many more beneficial and important practical solutions. The availability of all the solutions provides the opportunity to further characterize, rank and select the most appropriate intervention strategy based on any desired evaluation index. Our implementation of the FastKnock method in Python is publicly available at https://github.com/leilahsn/FastKnock .

FastKnock: An efficient next-generation approach to identify all knockout strategies for strain optimization

Overproduction of desired native or nonnative biochemical(s) in (micro)organisms can be achieved through metabolic engineering. Appropriate rewiring of cell metabolism is performed making rational changes such as insertion, up-/down-regulation and knockout of genes and consequently metabolic reactions. Finding appropriate targets (including proper sets of reactions to be knocked out) for metabolic engineering to design optimal production strains has been the goal of a number of computational algorithms. We developed FastKnock, an efficient next-generation algorithm for identifying all possible knockout strategies for the growth-coupled overproduction of biochemical(s) of interest. We achieve this by developing a special depth-first traversal algorithm that allows us to prune the search space significantly. This leads to a drastic reduction in execution time. We evaluate the performance of the FastKnock algorithm using three Escherichia coli genome-scale metabolic models in different conditions (minimal and rich mediums) for the overproduction of a number of desired metabolites. FastKnock efficiently prunes the search space to less than 0.2% for quadruple and 0.02% for quintuple-reaction knockouts. Compared to the classic approaches such as OptKnock and the state-of-the-art techniques such as MCSEnumerator methods, FastKnock found many more useful and important practical solutions. The availability of all the solutions provides the opportunity to further characterize and select the most appropriate intervention strategy based on any desired evaluation index. Our implementation of the FastKnock method in Python is publicly available at https://github.com/leilahsn/FastKnock.

Speeding Up the Structural Analysis of Metabolic Network Models Using the Fredman-Khachiyan Algorithm B

The problem of computing the Elementary Flux Modes (EFMs) and Minimal Cut Sets (MCSs) of metabolic network is a fundamental one in metabolic networks. A key insight is that they can be understood as a dual pair of monotone Boolean functions (MBFs). Using this insight, this computation reduces to the question of generating from an oracle a dual pair of MBFs. If one of the two sets (functions) is known, then the other can be computed through a process known as dualization. Fredman and Khachiyan provided two algorithms, which they called simply A and B that can serve as an engine for oracle-based generation or dualization of MBFs. We look at efficiencies available in implementing their algorithm B, which we will refer to as FK-B. Like their algorithm A, FK-B certifies whether two given MBFs in the form of Conjunctive Normal Form and Disjunctive Normal Form are dual or not, and in case of not being dual it returns a conflicting assignment (CA), that is, an assignment that makes one of the given Boolean functions True and the other one False. The FK-B algorithm is a recursive algorithm that searches through the tree of assignments to find a CA. If it does not find any CA, it means that the given Boolean functions are dual. In this article, we propose six techniques applicable to the FK-B and hence to the dualization process. Although these techniques do not reduce the time complexity, they considerably reduce the running time in practice. We evaluate the proposed improvements by applying them to compute the MCSs from the EFMs in the 19 small- and medium-sized models from the BioModels database along with 4 models of biomass synthesis in Escherichia coli that were used in an earlier computational survey Haus et al. (2008).

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.

Multiple Levels of Heuristic Reasoning Processes in Scientific Model Construction

Science historians have recognized the importance of heuristic reasoning strategies for constructing theories, but their extent and degree of organization are still poorly understood. This paper first consolidates a set of important heuristic strategies for constructing scientific models from three books, including studies in the history of genetics and electromagnetism, and an expert think-aloud study in the field of mechanics. The books focus on qualitative reasoning strategies (processes) involved in creative model construction, scientific breakthroughs, and conceptual change. Twenty four processes are examined, most of which are field-general, but all are heuristic in not being guaranteed to work. An organizing framework is then proposed as a four-level hierarchy of nested reasoning processes and subprocesses at different size and time scales, including: Level (L4) Several longer-time-scale Major Modeling Modes, such as Model Evolution and Model Competition; the former mode utilizes: (L3) Modeling Cycle Phases of Model Generation, Evaluation, and Modification under Constraints; which can utilize: (L2) Thirteen Tactical Heuristic Processes, e.g., Analogy, Infer new model feature (e.g., by running the model), etc.; many of which selectively utilize: (L1) Grounded Imagistic Processes, namely Mental Simulations and Structural Transformations. Incomplete serial ordering in the framework gives it an intermediate degree of organization that is neither anarchistic nor fully algorithmic. Its organizational structure is hypothesized to promote a difficult balance between divergent and convergent processes as it alternates between them in modeling cycles with increasingly constrained modifications. Videotaped think-aloud protocols that include depictive gestures and other imagery indicators indicate that the processes in L1 above can be imagistic. From neurological evidence that imagery uses many of the same brain regions as actual perception and action, it is argued that these expert reasoning processes are grounded in the sense of utilizing the perceptual and motor systems, and interconnections to and possible benefits for reasoning processes at higher levels are examined. The discussion examines whether this grounding and the various forms of organization in the framework may begin to explain how processes that are only sometimes useful and not guaranteed to work can combine successfully to achieve innovative scientific model construction.

Systematizing the different notions of growth-coupled product synthesis and a single framework for computing corresponding strain designs

A widely used design principle for metabolic engineering of microorganisms aims to introduce interventions that enforce growth-coupled product synthesis such that the product of interest becomes a (mandatory) by-product of growth. However, different variants and partially contradicting notions of growth-coupled production (GCP) exist. Herein, we propose an ontology for the different degrees of GCP and clarify their relationships. Ordered by coupling degree, we distinguish four major classes: potentially, weakly, and directionally growth-coupled production (pGCP, wGCP, dGCP) as well as substrate-uptake coupled production (SUCP). We then extend the framework of Minimal Cut Sets (MCS), previously used to compute dGCP and SUCP strain designs, to allow inclusion of implicit optimality constraints, a feature required to compute pGCP and wGCP designs. This extension closes the gap between MCS-based and bilevel-based strain design approaches and enables computation (and comparison) of designs for all GCP classes within a single framework. By computing GCP strain designs for a range of products, we illustrate the hierarchical relationships between the different coupling degrees. We find that feasibility of coupling is not affected by the chosen GCP degree and that strongest coupling (SUCP) requires often only one or two more interventions than wGCP and dGCP. Finally, we show that the principle of coupling can be generalized to couple product synthesis with other cellular functions than growth, for example, with net ATP formation. This work provides important theoretical results and algorithmic developments and a unified terminology for computational strain design based on GCP.

Modelling Cell Metabolism: A Review on Constraint-Based Steady-State and Kinetic Approaches

Studying cell metabolism serves a plethora of objectives such as the enhancement of bioprocess performance, and advancement in the understanding of cell biology, of drug target discovery, and in metabolic therapy. Remarkable successes in these fields emerged from heuristics approaches, for instance, with the introduction of effective strategies for genetic modifications, drug developments and optimization of bioprocess management. However, heuristics approaches have showed significant shortcomings, such as to describe regulation of metabolic pathways and to extrapolate experimental conditions. In the specific case of bioprocess management, such shortcomings limit their capacity to increase product quality, while maintaining desirable productivity and reproducibility levels. For instance, since heuristics approaches are not capable of prediction of the cellular functions under varying experimental conditions, they may lead to sub-optimal processes. Also, such approaches used for bioprocess control often fail in regulating a process under unexpected variations of external conditions. Therefore, methodologies inspired by the systematic mathematical formulation of cell metabolism have been used to address such drawbacks and achieve robust reproducible results. Mathematical modelling approaches are effective for both the characterization of the cell physiology, and the estimation of metabolic pathways utilization, thus allowing to characterize a cell population metabolic behavior. In this article, we present a review on methodology used and promising mathematical modelling approaches, focusing primarily to investigate metabolic events and regulation. Proceeding from a topological representation of the metabolic networks, we first present the metabolic modelling approaches that investigate cell metabolism at steady state, complying to the constraints imposed by mass conservation law and thermodynamics of reactions reversibility. Constraint-based models (CBMs) are reviewed highlighting the set of assumed optimality functions for reaction pathways. We explore models simulating cell growth dynamics, by expanding flux balance models developed at steady state. Then, discussing a change of metabolic modelling paradigm, we describe dynamic kinetic models that are based on the mathematical representation of the mechanistic description of nonlinear enzyme activities. In such approaches metabolic pathway regulations are considered explicitly as a function of the activity of other components of metabolic networks and possibly far from the metabolic steady state. We have also assessed the significance of metabolic model parameterization in kinetic models, summarizing a standard parameter estimation procedure frequently employed in kinetic metabolic modelling literature. Finally, some optimization practices used for the parameter estimation are reviewed.