Analysis of metabolic subnetworks by flux cone projection

A hierarchy of metabolite exchanges in metabolic models of microbial species and communities

The metabolic network of an organism can be analyzed as a constraint-based model. This analysis can be biased, optimizing an objective such as growth rate, or unbiased, aiming to describe the full feasible space of metabolic fluxes through pathway analysis or random flux sampling. In particular, pathway analysis can decompose the flux space into fundamental and formally defined metabolic pathways. Unbiased methods scale poorly with network size due to combinatorial explosion, but a promising approach to improve scalability is to focus on metabolic subnetworks, e.g., cells' metabolite exchanges with each other and the environment, rather than the full metabolic networks. Here, we applied pathway enumeration and flux sampling to metabolite exchanges in microbial species and a microbial community, using models ranging from central carbon metabolism to genome-scale and focusing on pathway definitions that allow direct targeting of subnetworks such as metabolite exchanges (elementary conversion modes, elementary flux patterns, and minimal pathways). Enumerating growth-supporting metabolite exchanges, we found that metabolite exchanges from different pathway definitions were related through a hierarchy, and we show that this hierarchical relationship between pathways holds for metabolic networks and subnetworks more generally. Metabolite exchange frequencies, defined as the fraction of pathways in which each metabolite was exchanged, were similar across pathway definitions, with a few specific exchanges explaining large differences in pathway counts. This indicates that biological interpretation of predicted metabolite exchanges is robust to the choice of pathway definition, and it suggests strategies for more scalable pathway analysis. Our results also signal wider biological implications, facilitating detailed and interpretable analysis of metabolite exchanges and other subnetworks in fields such as metabolic engineering and synthetic biology.

On the representativeness and stability of a set of EFMs

MOTIVATION

Elementary flux modes are a well-known tool for analyzing metabolic networks. The whole set of elementary flux modes (EFMs) cannot be computed in most genome-scale networks due to their large cardinality. Therefore, different methods have been proposed to compute a smaller subset of EFMs that can be used for studying the structure of the network. These latter methods pose the problem of studying the representativeness of the calculated subset. In this article, we present a methodology to tackle this problem.

RESULTS

We have introduced the concept of stability for a particular network parameter and its relation to the representativeness of the EFM extraction method studied. We have also defined several metrics to study and compare the EFM biases. We have applied these techniques to compare the relative behavior of previously proposed methods in two case studies. Furthermore, we have presented a new method for the EFM computation (PiEFM), which is more stable (less biased) than previous ones, has suitable representativeness measures, and exhibits better variability in the extracted EFMs.

AVAILABILITY AND IMPLEMENTATION

Software and additional material are freely available at https://github.com/biogacop/PiEFM.

EFMlrs: a Python package for elementary flux mode enumeration via lexicographic reverse search

Background

Elementary flux mode (EFM) analysis is a well-established, yet computationally challenging approach to characterize metabolic networks. Standard algorithms require huge amounts of memory and lack scalability which limits their application to single servers and consequently limits a comprehensive analysis to medium-scale networks. Recently, Avis et al. developed mplrs—a parallel version of the lexicographic reverse search (lrs) algorithm, which, in principle, enables an EFM analysis on high-performance computing environments (Avis and Jordan. mplrs: a scalable parallel vertex/facet enumeration code. arXiv:1511.06487, 2017). Here we test its applicability for EFM enumeration.

Results

We developed EFMlrs, a Python package that gives users access to the enumeration capabilities of mplrs. EFMlrs uses COBRApy to process metabolic models from sbml files, performs loss-free compressions of the stoichiometric matrix, and generates suitable inputs for mplrs as well as efmtool, providing support not only for our proposed new method for EFM enumeration but also for already established tools. By leveraging COBRApy, EFMlrs also allows the application of additional reaction boundaries and seamlessly integrates into existing workflows.

Conclusion

We show that due to mplrs’s properties, the algorithm is perfectly suited for high-performance computing (HPC) and thus offers new possibilities for the unbiased analysis of substantially larger metabolic models via EFM analyses. EFMlrs is an open-source program that comes together with a designated workflow and can be easily installed via pip.

Supplementary Information

The online version contains supplementary material available at 10.1186/s12859-021-04417-9.

Unlocking Elementary Conversion Modes: ecmtool Unveils All Capabilities of Metabolic Networks

The metabolic capabilities of cells determine their biotechnological potential, fitness in ecosystems, pathogenic threat levels, and function in multicellular organisms. Their comprehensive experimental characterization is generally not feasible, particularly for unculturable organisms. In principle, the full range of metabolic capabilities can be computed from an organism's annotated genome using metabolic network reconstruction. However, current computational methods cannot deal with genome-scale metabolic networks. Part of the problem is that these methods aim to enumerate all metabolic pathways, while computation of all (elementally balanced) conversions between nutrients and products would suffice. Indeed, the elementary conversion modes (ECMs, defined by Urbanczik and Wagner) capture the full metabolic capabilities of a network, but the use of ECMs has not been accessible until now. We explain and extend the theory of ECMs, implement their enumeration in ecmtool, and illustrate their applicability. This work contributes to the elucidation of the full metabolic footprint of any cell.

•

Elementary conversion modes (ECMs) specify all metabolic capabilities of any organism

•

Ecmtool computes all ECMs from a reconstructed metabolic network

•

ECM enumeration enables metabolic characterization of larger networks than ever

•

Focusing on ECMs between relevant metabolites even enables genome-scale enumeration

Understanding the metabolic capabilities of cells is of profound importance. Microbial metabolism shapes global cycles of elements and cleans polluted soils. Human and pathogen metabolism affects our health. Recent advances allow for automatic reconstruction of reaction networks for any organism, which is already used in synthetic biology, (food) microbiology, and agriculture to compute optimal yields from resources to products. However, computational tools are limited to optimal states or subnetworks, leaving many capabilities of organisms hidden. Our program, ecmtool, creates a blueprint of any organism's metabolic functionalities, drastically improving insights obtained from genome sequences. Ecmtool may become essential in exploratory research, especially for studying cells that are not culturable in laboratory conditions. Ideally, elementary conversion mode enumeration will someday be a standard step after metabolic network reconstruction, achieving the metabolic characterization of all known organisms.

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.

Sequential computation of elementary modes and minimal cut sets in genome-scale metabolic networks using alternate integer linear programming

Motivation

Elementary (flux) modes (EMs) have served as a valuable tool for investigating structural and functional properties of metabolic networks. Identification of the full set of EMs in genome-scale networks remains challenging due to combinatorial explosion of EMs in complex networks. It is often, however, that only a small subset of relevant EMs needs to be known, for which optimization-based sequential computation is a useful alternative. Most of the currently available methods along this line are based on the iterative use of mixed integer linear programming (MILP), the effectiveness of which significantly deteriorates as the number of iterations builds up. To alleviate the computational burden associated with the MILP implementation, we here present a novel optimization algorithm termed alternate integer linear programming (AILP).

Results

Our algorithm was designed to iteratively solve a pair of integer programming (IP) and linear programming (LP) to compute EMs in a sequential manner. In each step, the IP identifies a minimal subset of reactions, the deletion of which disables all previously identified EMs. Thus, a subsequent LP solution subject to this reaction deletion constraint becomes a distinct EM. In cases where no feasible LP solution is available, IP-derived reaction deletion sets represent minimal cut sets (MCSs). Despite the additional computation of MCSs, AILP achieved significant time reduction in computing EMs by orders of magnitude. The proposed AILP algorithm not only offers a computational advantage in the EM analysis of genome-scale networks, but also improves the understanding of the linkage between EMs and MCSs.

Availability and Implementation

The software is implemented in Matlab, and is provided as supplementary information .

Contact

hyunseob.song@pnnl.gov.

Supplementary information

Supplementary data are available at Bioinformatics online.

Genome-scale reconstruction of the metabolic network in Pseudomonas stutzeri A1501

Pseudomonas stutzeri A1501 is an endophytic bacterium capable of nitrogen fixation. This strain has been isolated from the rice rhizosphere and provides the plant with fixed nitrogen and phytohormones. These interesting features encouraged us to study the metabolism of this microorganism at the systems-level. In this work, we present the first genome-scale metabolic model (iPB890) for P. stutzeri, involving 890 genes, 1135 reactions, and 813 metabolites. A combination of automatic and manual approaches was used in the reconstruction process. Briefly, using the metabolic networks of Pseudomonas aeruginosa and Pseudomonas putida as templates, a draft metabolic network of P. stutzeri was reconstructed. Then, the draft network was driven through an iterative and curative process of gap filling. In the next step, the model was evaluated using different experimental data such as specific growth rate, Biolog substrate utilization data and other experimental observations. In most of the evaluation cases, the model was successful in correctly predicting the cellular phenotypes. Thus, we posit that the iPB890 model serves as a suitable platform to explore the metabolism of P. stutzeri.

Elementary Vectors and Conformal Sums in Polyhedral Geometry and their Relevance for Metabolic Pathway Analysis

A fundamental result in metabolic pathway analysis states that every flux mode can be decomposed into a sum of elementary modes. However, only a decomposition without cancelations is biochemically meaningful, since a reversible reaction cannot have different directions in the contributing elementary modes. This essential requirement has been largely overlooked by the metabolic pathway community. Indeed, every flux mode can be decomposed into elementary modes without cancelations. The result is an immediate consequence of a theorem by Rockafellar which states that every element of a linear subspace is a conformal sum (a sum without cancelations) of elementary vectors (support-minimal vectors). In this work, we extend the theorem, first to “subspace cones” and then to general polyhedral cones and polyhedra. Thereby, we refine Minkowski's and Carathéodory's theorems, two fundamental results in polyhedral geometry. We note that, in general, elementary vectors need not be support-minimal; in fact, they are conformally non-decomposable and form a unique minimal set of conformal generators. Our treatment is mathematically rigorous, but suitable for systems biologists, since we give self-contained proofs for our results and use concepts motivated by metabolic pathway analysis. In particular, we study cones defined by linear subspaces and nonnegativity conditions — like the flux cone — and use them to analyze general polyhedral cones and polyhedra. Finally, we review applications of elementary vectors and conformal sums in metabolic pathway analysis.

gEFM: An Algorithm for Computing Elementary Flux Modes Using Graph Traversal

Computational methods to engineer cellular metabolism promise to play a critical role in producing pharmaceutical, repairing defective genes, destroying cancer cells, and generating biofuels. Elementary Flux Mode (EFM) analysis is one such powerful technique that has elucidated cell growth and regulation, predicted product yield, and analyzed network robustness. EFM analysis, however, is a computationally daunting task because it requires the enumeration of all independent and stoichiometrically balanced pathways within a cellular network. We present in this paper an EFM enumeration algorithm, termed graphical EFM or gEFM. The algorithm is based on graph traversal, an approach previously assumed unsuitable for enumerating EFMs. The approach is derived from a pathway synthesis method proposed by Mavrovouniotis et al. The algorithm is described and proved correct. We apply gEFM to several networks and report runtimes in comparison with other EFM computation tools. We show how gEFM benefits from network compression. Like other EFM computational techniques, gEFM is sensitive to constraint ordering; however, we are able to demonstrate that knowledge of the underlying network structure leads to better constraint ordering. gEFM is shown to be competitive with state-of-the-art EFM computational techniques for several networks, but less so for networks with a larger number of EFMs.

Exploiting stoichiometric redundancies for computational efficiency and network reduction

Analysis of metabolic networks typically begins with construction of the stoichiometry matrix, which characterizes the network topology. This matrix provides, via the balance equation, a description of the potential steady-state flow distribution. This paper begins with the observation that the balance equation depends only on the structure of linear redundancies in the network, and so can be stated in a succinct manner, leading to computational efficiencies in steady-state analysis. This alternative description of steady-state behaviour is then used to provide a novel method for network reduction, which complements existing algorithms for describing intracellular networks in terms of input-output macro-reactions (to facilitate bioprocess optimization and control). Finally, it is demonstrated that this novel reduction method can be used to address elementary mode analysis of large networks: the modes supported by a reduced network can capture the input-output modes of a metabolic module with significantly reduced computational effort.

Finding elementary flux modes in metabolic networks based on flux balance analysis and flux coupling analysis: application to the analysis of Escherichia coli metabolism

Elementary modes (EMs) are steady-state metabolic flux vectors with minimal set of active reactions. Each EM corresponds to a metabolic pathway. Therefore, studying EMs is helpful for analyzing the production of biotechnologically important metabolites. However, memory requirements for computing EMs may hamper their applicability as, in most genome-scale metabolic models, no EM can be computed due to running out of memory. In this study, we present a method for computing randomly sampled EMs. In this approach, a network reduction algorithm is used for EM computation, which is based on flux balance-based methods. We show that this approach can be used to recover the EMs in the medium- and genome-scale metabolic network models, while the EMs are sampled in an unbiased way. The applicability of such results is shown by computing “estimated” control-effective flux values in Escherichia coli metabolic network.