Fast computation of minimal cut sets in metabolic networks with a Berge algorithm that utilizes binary bit pattern trees

Adding metabolic tasks to human GEM models to improve the study of gene targets and their associated toxicities

Genetic minimal cut sets (gMCS) are genes that must be deactivated simultaneously to avoid unwanted states in a metabolic model. The concept of gMCS can be applied to two different scenarios. First, it can be used to identify potential gene toxicities in generic or healthy cell models. Second, it can be used to develop genetic strategies to target cancer cells and prevent their proliferation. Up to now, gMCS have been evaluated using the traditional procedure of preventing biomass production. This paper proposes an additional way: using essential metabolic tasks, which any human cell should perform, to enlarge the set of unwanted states. Including this addition can significantly improve the study of toxicities and reveal targets that can be used to treat unhealthy cells. Excluding metabolic tasks can cause important information to be overlooked, which could impact the study's success. Regarding toxicities, using the generic Human model, the number of detected generic toxicities with metabolic tasks increases from 106 to 281 (136 gMCSs of length 1 and 49 of length 2). We have used the following context-specific models to evaluate specific toxicities in different healthy tissues: blood, pancreas, liver, heart, and kidney. Again, considering metabolic tasks, we have found new toxicities (lengths 1 and 2) whose inactivation could damage these healthy tissues.Our research strategy has been applied to identify new cancer drug targets in two myeloma cell lines. We obtained new therapeutic targets of lengths 1 and 2 for each cell line. After analyzing the data, we conclude that incorporating metabolic tasks into cancer models can reveal important therapeutic targets previously disregarded by the conventional method of inhibiting biomass production. This approach also improves the evaluation of potential drug toxicities.

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.

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

MOTIVATION

Minimal cut sets (MCSs) for metabolic networks are sets of reactions which, if they are removed from the network, prevent a target reaction from carrying flux. To compute MCSs different methods exist, which may fail to find sufficiently many MCSs for larger genome-scale networks.

RESULTS

Here we introduce irreversible minimal cut sets (iMCSs). These are MCSs that consist of irreversible reactions only. The advantage of iMCSs is that they can be computed by projecting the flux cone of the metabolic network on the set of irreversible reactions, which usually leads to a smaller cone. Using oriented matroid theory, we show how the projected cone can be computed efficiently and how this can be applied to find iMCSs even in large genome-scale networks.

AVAILABILITY AND IMPLEMENTATION

Software is freely available at https://sourceforge.net/projects/irreversibleminimalcutsets/.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Designing Optimized Production Hosts by Metabolic Modeling

Many of the complex and expensive production steps in the chemical industry are readily available in living cells. In order to overcome the metabolic limits of these cells, the optimal genetic intervention strategies can be computed by the use of metabolic modeling. Elementary flux mode analysis (EFMA) is an ideal tool for this task, as it does not require defining a cellular objective function. We present two EFMA-based methods to optimize production hosts: (1) the standard approach that can only be used for small and medium scale metabolic networks and (2) the advanced dual system approach that can be utilized to directly compute intervention strategies in a genome-scale metabolic model.

Development of a Framework for Metabolic Pathway Analysis-Driven Strain Optimization Methods

Genome-scale metabolic models (GSMMs) have become important assets for rational design of compound overproduction using microbial cell factories. Most computational strain optimization methods (CSOM) using GSMMs, while useful in metabolic engineering, rely on the definition of questionable cell objectives, leading to some bias. Metabolic pathway analysis approaches do not require an objective function. Though their use brings immediate advantages, it has mostly been restricted to small scale models due to computational demands. Additionally, their complex parameterization and lack of intuitive tools pose an important challenge towards making these widely available to the community. Recently, MCSEnumerator has extended the scale of these methods, namely regarding enumeration of minimal cut sets, now able to handle GSMMs. This work proposes a tool implementing this method as a Java library and a plugin within the OptFlux metabolic engineering platform providing a friendly user interface. A standard enumeration problem and pipeline applicable to GSMMs is proposed, making use by the community simpler. To highlight the potential of these approaches, we devised a case study for overproduction of succinate, providing a phenotype analysis of a selected strategy and comparing robustness with a selected solution from a bi-level CSOM.

Designing minimal microbial strains of desired functionality using a genetic algorithm

Background

The rational, in silico prediction of gene-knockouts to turn organisms into efficient cell factories is an essential and computationally challenging task in metabolic engineering. Elementary flux mode analysis in combination with constraint minimal cut sets is a particularly powerful method to identify optimal engineering targets, which will force an organism into the desired metabolic state. Given an engineering objective, it is theoretically possible, although computationally impractical, to find the best minimal intervention strategies.

Results

We developed a genetic algorithm (GA-MCS) to quickly find many (near) optimal intervention strategies while overcoming the above mentioned computational burden. We tested our algorithm on Escherichia coli metabolic networks of three different sizes to find intervention strategies satisfying three different engineering objectives.

Conclusions

We show that GA-MCS finds all practically relevant targets for any (non)-linear engineering objective. Our algorithm also found solutions comparable to previously published results. We show that for large networks optimal solutions are found within a fraction of the time used for a complete enumeration.

Rational design of efficient modular cells

The modular cell design principle is formulated to devise modular (chassis) cells. These cells can be assembled with exchangeable production modules in a plug-and-play fashion to build microbial cell factories for efficient combinatorial biosynthesis of novel molecules, requiring minimal iterative strain optimization steps. A modular cell is designed to be auxotrophic, containing core metabolic pathways that are necessary but insufficient to support cell growth and maintenance. To be functional, it must tightly couple with an exchangeable production module containing auxiliary metabolic pathways that not only complement cell growth but also enhance production of targeted molecules. We developed a MODCELL (modular cell) framework based on metabolic pathway analysis to implement the modular cell design principle. MODCELL identifies genetic modifications and requirements to construct modular cell candidates and their associated exchangeable production modules. By defining the degree of similarity and coupling metrics, MODCELL can evaluate which exchangeable production module(s) can be tightly coupled with a modular cell candidate. We first demonstrated how MODCELL works in a step-by-step manner for example metabolic networks, and then applied it to design modular Escherichia coli cells for efficient combinatorial biosynthesis of five alcohols (ethanol, propanol, isopropanol, butanol and isobutanol) and five butyrate esters (ethyl butyrate, propyl butyrate, isopropyl butyrate, butyl butyrate and isobutyl butyrate) from pentose sugars (arabinose and xylose) and hexose sugars (glucose, mannose, and galactose) under anaerobic conditions. We identified three modular cells, MODCELL1, MODCELL2 and MODCELL3, that can couple well with Group 1 of modules (ethanol, isobutanol, butanol, ethyl butyrate, isobutyl butyrate, butyl butyrate), Group 2 (isopropanol, isopropyl butyrate), and Group 3 (propanol, isopropanol), respectively. We validated the design of MODCELL1 for anaerobic production of ethanol, butanol, and ethyl butyrate using experimental data available in literature.

Avoiding the Enumeration of Infeasible Elementary Flux Modes by Including Transcriptional Regulatory Rules in the Enumeration Process Saves Computational Costs

Despite the significant progress made in recent years, the computation of the complete set of elementary flux modes of large or even genome-scale metabolic networks is still impossible. We introduce a novel approach to speed up the calculation of elementary flux modes by including transcriptional regulatory information into the analysis of metabolic networks. Taking into account gene regulation dramatically reduces the solution space and allows the presented algorithm to constantly eliminate biologically infeasible modes at an early stage of the computation procedure. Thereby, computational costs, such as runtime, memory usage, and disk space, are extremely reduced. Moreover, we show that the application of transcriptional rules identifies non-trivial system-wide effects on metabolism. Using the presented algorithm pushes the size of metabolic networks that can be studied by elementary flux modes to new and much higher limits without the loss of predictive quality. This makes unbiased, system-wide predictions in large scale metabolic networks possible without resorting to any optimization principle.