On algebraic properties of extreme pathways in metabolic networks

Basic pathway decomposition of biochemical reaction networks within growing cells

This contribution treats linear, steady-state dynamics for a metabolic network within a growing cell. Admissible steady-state reaction fluxes are assumed to form a pointed, convex, polyhedral, conical subset of the stoichiometric null-space. A solution of the problem is defined to consist of a linear basis for the stoichiometric null-space consisting of admissible fluxes called basic pathways. The algorithm used to construct the set of basic pathways scales as a polynomial of the system size in contrast to the NP-hard algorithms employed in the traditional notions of solution named extreme pathways, elementary flux modes, MEMos, and MinSpan, and that therefore suffer from the curse of dimensionality. The basic pathways approach is applied to a metabolic network consisting of a simplified version of the TCA cycle coupled to glycolysis highlighting that each basic pathway has a readily understood chemical interpretation. Generic admissible pathways are simply expressed in terms of basic pathways.

On the geometry of elementary flux modes

Elementary flux modes (EFMs) play a prominent role in the constraint-based analysis of metabolic networks. They correspond to minimal functional units of the metabolic network at steady-state and as such have been studied for almost 30 years. The set of all EFMs in a metabolic network tends to be very large and may have exponential size in the number of reactions. Hence, there is a need to elucidate the structure of this set. Here we focus on geometric properties of EFMs. We analyze the distribution of EFMs in the face lattice of the steady-state flux cone of the metabolic network and show that EFMs in the relative interior of the cone occur only in very special cases. We introduce the concept of degree of an EFM as a measure how elementary it is and study the decomposition of flux vectors and EFMs depending on their degree. Geometric analysis can help to better understand the structure of the set of EFMs, which is important from both the mathematical and the biological viewpoint.

Towards scaling elementary flux mode computation

While elementary flux mode (EFM) analysis is now recognized as a cornerstone computational technique for cellular pathway analysis and engineering, EFM application to genome-scale models remains computationally prohibitive. This article provides a review of aspects of EFM computation that elucidates bottlenecks in scaling EFM computation. First, algorithms for computing EFMs are reviewed. Next, the impact of redundant constraints, sensitivity to constraint ordering and network compression are evaluated. Then, the advantages and limitations of recent parallelization and GPU-based efforts are highlighted. The article then reviews alternative pathway analysis approaches that aim to reduce the EFM solution space. Despite advances in EFM computation, our review concludes that continued scaling of EFM computation is necessary to apply EFM to genome-scale models. Further, our review concludes that pathway analysis methods that target specific pathway properties can provide powerful alternatives to EFM analysis.

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.

Efficient estimation of the maximum metabolic productivity of batch systems

BACKGROUND

Production of chemicals from engineered organisms in a batch culture involves an inherent trade-off between productivity, yield, and titer. Existing strategies for strain design typically focus on designing mutations that achieve the highest yield possible while maintaining growth viability. While these methods are computationally tractable, an optimum productivity could be achieved by a dynamic strategy in which the intracellular division of resources is permitted to change with time. New methods for the design and implementation of dynamic microbial processes, both computational and experimental, have therefore been explored to maximize productivity. However, solving for the optimal metabolic behavior under the assumption that all fluxes in the cell are free to vary is a challenging numerical task. Previous studies have therefore typically focused on simpler strategies that are more feasible to implement in practice, such as the time-dependent control of a single flux or control variable.

RESULTS

This work presents an efficient method for the calculation of a maximum theoretical productivity of a batch culture system using a dynamic optimization framework. The proposed method follows traditional assumptions of dynamic flux balance analysis: first, that internal metabolite fluxes are governed by a pseudo-steady state, and secondly that external metabolite fluxes are dynamically bounded. The optimization is achieved via collocation on finite elements, and accounts explicitly for an arbitrary number of flux changes. The method can be further extended to calculate the complete Pareto surface of productivity as a function of yield. We apply this method to succinate production in two engineered microbial hosts, Escherichia coli and Actinobacillus succinogenes, and demonstrate that maximum productivities can be more than doubled under dynamic control regimes.

CONCLUSIONS

The maximum theoretical yield is a measure that is well established in the metabolic engineering literature and whose use helps guide strain and pathway selection. We present a robust, efficient method to calculate the maximum theoretical productivity: a metric that will similarly help guide and evaluate the development of dynamic microbial bioconversions. Our results demonstrate that nearly optimal yields and productivities can be achieved with only two discrete flux stages, indicating that near-theoretical productivities might be achievable in practice.

A depth-first search algorithm to compute elementary flux modes by linear programming

Background

The decomposition of complex metabolic networks into elementary flux modes (EFMs) provides a useful framework for exploring reaction interactions systematically. Generating a complete set of EFMs for large-scale models, however, is near impossible. Even for moderately-sized models (<400 reactions), existing approaches based on the Double Description method must iterate through a large number of combinatorial candidates, thus imposing an immense processor and memory demand.

Results

Based on an alternative elementarity test, we developed a depth-first search algorithm using linear programming (LP) to enumerate EFMs in an exhaustive fashion. Constraints can be introduced to directly generate a subset of EFMs satisfying the set of constraints. The depth-first search algorithm has a constant memory overhead. Using flux constraints, a large LP problem can be massively divided and parallelized into independent sub-jobs for deployment into computing clusters. Since the sub-jobs do not overlap, the approach scales to utilize all available computing nodes with minimal coordination overhead or memory limitations.

Conclusions

The speed of the algorithm was comparable to efmtool, a mainstream Double Description method, when enumerating all EFMs; the attrition power gained from performing flux feasibility tests offsets the increased computational demand of running an LP solver. Unlike the Double Description method, the algorithm enables accelerated enumeration of all EFMs satisfying a set of constraints.

Elementary flux modes in a nutshell: properties, calculation and applications

Elementary flux mode (EFM) analysis allows the unbiased decomposition of a metabolic network into minimal functional units, making it a powerful tool for metabolic engineering. While the use of EFM analysis (EFMA) is still limited by the size of the models it can handle, EFMA has been successfully applied to solve real-world metabolic engineering problems. Here we provide a user-oriented introduction to EFMA, provide examples of recent applications, analyze current research strategies to overcome the computational restrictions and give an overview over current approaches, which aim to identify and calculate only biologically relevant EFMs.

Finding minimal generating set for metabolic network with reversible pathways

Elementary flux modes give a mathematical representation of metabolic pathways in metabolic networks satisfying the constraint of non-decomposability. The large cost of their computation shifts attention to computing a minimal generating set which is a conically independent subset of elementary flux modes. When a metabolic network has reversible reactions and also admits a reversible pathway, the minimal generating set is not unique. A theoretical development and computational framework is provided which outline how to compute the minimal generating set in this case. The method is based on combining existing software to compute the minimal generating set for a "pointed cone" together with standard software to compute the Reduced Row Echelon Form.

Elucidating and reprogramming Escherichia coli metabolisms for obligate anaerobic n-butanol and isobutanol production

Elementary mode (EM) analysis based on the constraint-based metabolic network modeling was applied to elucidate and compare complex fermentative metabolisms of Escherichia coli for obligate anaerobic production of n-butanol and isobutanol. The result shows that the n-butanol fermentative metabolism was NADH-deficient, while the isobutanol fermentative metabolism was NADH redundant. E. coli could grow and produce n-butanol anaerobically as the sole fermentative product but not achieve the maximum theoretical n-butanol yield. In contrast, for the isobutanol fermentative metabolism, E. coli was required to couple with either ethanol- or succinate-producing pathway to recycle NADH. To overcome these "defective" metabolisms, EM analysis was implemented to reprogram the native fermentative metabolism of E. coli for optimized anaerobic production of n-butanol and isobutanol through multiple gene deletion (~8-9 genes), addition (~6-7 genes), up- and downexpression (~6-7 genes), and cofactor engineering (e.g., NADH, NADPH). The designed strains were forced to couple both growth and anaerobic production of n-butanol and isobutanol, which is a useful characteristic to enhance biofuel production and tolerance through metabolic pathway evolution. Even though the n-butanol and isobutanol fermentative metabolisms were quite different, the designed strains could be engineered to have identical metabolic flux distribution in "core" metabolic pathways mainly supporting cell growth and maintenance. Finally, the model prediction in elucidating and reprogramming the native fermentative metabolism of E. coli for obligate anaerobic production of n-butanol and isobutanol was validated with published experimental data.

Analysis of metabolic subnetworks by flux cone projection

Background

Analysis of elementary modes (EMs) is proven to be a powerful constraint-based method in the study of metabolic networks. However, enumeration of EMs is a hard computational task. Additionally, due to their large number, EMs cannot be simply used as an input for subsequent analysis. One possibility is to limit the analysis to a subset of interesting reactions. However, analysing an isolated subnetwork can result in finding incorrect EMs which are not part of any steady-state flux distribution of the original network. The ideal set to describe the reaction activity in a subnetwork would be the set of all EMs projected to the reactions of interest. Recently, the concept of "elementary flux patterns" (EFPs) has been proposed. Each EFP is a subset of the support (i.e., non-zero elements) of at least one EM.

Results

We introduce the concept of ProCEMs (Projected Cone Elementary Modes). The ProCEM set can be computed by projecting the flux cone onto a lower-dimensional subspace and enumerating the extreme rays of the projected cone. In contrast to EFPs, ProCEMs are not merely a set of reactions, but projected EMs. We additionally prove that the set of EFPs is included in the set of ProCEM supports. Finally, ProCEMs and EFPs are compared for studying substructures of biological networks.

Conclusions

We introduce the concept of ProCEMs and recommend its use for the analysis of substructures of metabolic networks for which the set of EMs cannot be computed.

Elementary mode analysis: a useful metabolic pathway analysis tool for reprograming microbial metabolic pathways

Elementary mode analysis is a useful metabolic pathway analysis tool to characterize cellular metabolism. It can identify all feasible metabolic pathways known as elementary modes that are inherent to a metabolic network. Each elementary mode contains a minimal and unique set of enzymatic reactions that can support cellular functions at steady state. Knowledge of all these pathway options enables systematic characterization of cellular phenotypes, analysis of metabolic network properties (e.g. structure, regulation, robustness, and fragility), phenotypic behavior discovery, and rational strain design for metabolic engineering application. This chapter focuses on the application of elementary mode analysis to reprogram microbial metabolic pathways for rational strain design and the metabolic pathway evolution of designed strains.

Systems approaches to modelling pathways and networks

It has become commonly accepted that systems approaches to biology are of outstanding importance to gain understanding from the vast amount of data which is presently being generated by advancing high-throughput technologies. The diversity of methods to model pathways and networks has significantly expanded over the past two decades. Modern and traditional approaches are equally important and recent activities aim at integrating the advantages of both. While traditional methods, based on differential equations, are useful to study the dynamics of small systems, modern constraint-based models can be applied to genome-scale systems, but are not able to capture dynamic features. Integrating different approaches is important to develop consistent theoretical descriptions encompassing various scales of biological information. The rapid progress of the field of theoretical systems biology, however, demonstrates how our fundamental theoretical understanding of biology is gaining momentum. The scientific community has apparently accepted the challenge to truly understand the principles of life.

Parallelization of Nullspace Algorithm for the computation of metabolic pathways

Elementary mode analysis is a useful metabolic pathway analysis tool in understanding and analyzing cellular metabolism, since elementary modes can represent metabolic pathways with unique and minimal sets of enzyme-catalyzed reactions of a metabolic network under steady state conditions. However, computation of the elementary modes of a genome- scale metabolic network with 100-1000 reactions is very expensive and sometimes not feasible with the commonly used serial Nullspace Algorithm. In this work, we develop a distributed memory parallelization of the Nullspace Algorithm to handle efficiently the computation of the elementary modes of a large metabolic network. We give an implementation in C++ language with the support of MPI library functions for the parallel communication. Our proposed algorithm is accompanied with an analysis of the complexity and identification of major bottlenecks during computation of all possible pathways of a large metabolic network. The algorithm includes methods to achieve load balancing among the compute-nodes and specific communication patterns to reduce the communication overhead and improve efficiency.