Recovering metabolic pathways via optimization

Chemical Transformation Motifs-Modelling Pathways as Integer Hyperflows

We present an elaborate framework for formally modelling pathways in chemical reaction networks on a mechanistic level. Networks are modelled mathematically as directed multi-hypergraphs, with vertices corresponding to molecules and hyperedges to reactions. Pathways are modelled as integer hyperflows and we expand the network model by detailed routing constraints. In contrast to the more traditional approaches like Flux Balance Analysis or Elementary Mode analysis we insist on integer-valued flows. While this choice makes it necessary to solve possibly hard integer linear programs, it has the advantage that more detailed mechanistic questions can be formulated. It is thus possible to query networks for general transformation motifs, and to automatically enumerate optimal and near-optimal pathways. Similarities and differences between our work and traditional approaches in metabolic network analysis are discussed in detail. To demonstrate the applicability of the mathematical framework to real-life problems we first explore the design space of possible non-oxidative glycolysis pathways and show that recent manually designed pathways can be further optimized. We then use a model of sugar chemistry to investigate pathways in the autocatalytic formose process. A graph transformation-based approach is used to automatically generate the reaction networks of interest.

Identification of metabolic pathways using pathfinding approaches: a systematic review

Metabolic pathways have become increasingly available for various microorganisms. Such pathways have spurred the development of a wide array of computational tools, in particular, mathematical pathfinding approaches. This article can facilitate the understanding of computational analysis of metabolic pathways in genomics. Moreover, stoichiometric and pathfinding approaches in metabolic pathway analysis are discussed. Three major types of studies are elaborated: stoichiometric identification models, pathway-based graph analysis and pathfinding approaches in cellular metabolism. Furthermore, evaluation of the outcomes of the pathways with mathematical benchmarking metrics is provided. This review would lead to better comprehension of metabolism behaviors in living cells, in terms of computed pathfinding approaches.

FogLight: an efficient matrix-based approach to construct metabolic pathways by search space reduction

MOTIVATION

A fundamental computational problem in the area of metabolic engineering is finding metabolic pathways between a pair of source and target metabolites efficiently. We present an approach, namely FogLight, for searching metabolic networks utilizing Boolean (AND-OR) operations represented in matrix notation to efficiently reduce the search space. This enables the enumeration of all pathways between metabolites that are too distant for the application of brute-force methods.

RESULTS

Benchmarking tests run with FogLight show that it can reduce the search space by up to 98%, after which the accelerated search for high accurate results is guaranteed. Using FogLight, several pathways between eight given pairs of metabolites are found of which the pathways from CO2 to ethanol are specifically discussed. Additionally, in comparison with three path-finding tools, namely PHT, FMM and RouteSearch, FogLight can find shorter and more pathways for attempted source-target metabolite pairs.

CONTACT

szamani@aut.ac.ir, gholamreza.bidkhori@vtt.fi

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Integrating gene and protein expression data with genome-scale metabolic networks to infer functional pathways

Background

The study of cellular metabolism in the context of high-throughput -omics data has allowed us to decipher novel mechanisms of importance in biotechnology and health. To continue with this progress, it is essential to efficiently integrate experimental data into metabolic modeling.

Results

We present here an in-silico framework to infer relevant metabolic pathways for a particular phenotype under study based on its gene/protein expression data. This framework is based on the Carbon Flux Path (CFP) approach, a mixed-integer linear program that expands classical path finding techniques by considering additional biophysical constraints. In particular, the objective function of the CFP approach is amended to account for gene/protein expression data and influence obtained paths. This approach is termed integrative Carbon Flux Path (iCFP). We show that gene/protein expression data also influences the stoichiometric balancing of CFPs, which provides a more accurate picture of active metabolic pathways. This is illustrated in both a theoretical and real scenario. Finally, we apply this approach to find novel pathways relevant in the regulation of acetate overflow metabolism in Escherichia coli. As a result, several targets which could be relevant for better understanding of the phenomenon leading to impaired acetate overflow are proposed.

Conclusions

A novel mathematical framework that determines functional pathways based on gene/protein expression data is presented and validated. We show that our approach is able to provide new insights into complex biological scenarios such as acetate overflow in Escherichia coli.

Comparing methods for metabolic network analysis and an application to metabolic engineering

Bioinformatics tools have facilitated the reconstruction and analysis of cellular metabolism of various organisms based on information encoded in their genomes. Characterization of cellular metabolism is useful to understand the phenotypic capabilities of these organisms. It has been done quantitatively through the analysis of pathway operations. There are several in silico approaches for analyzing metabolic networks, including structural and stoichiometric analysis, metabolic flux analysis, metabolic control analysis, and several kinetic modeling based analyses. They can serve as a virtual laboratory to give insights into basic principles of cellular functions. This article summarizes the progress and advances in software and algorithm development for metabolic network analysis, along with their applications relevant to cellular physiology, and metabolic engineering with an emphasis on microbial strain optimization. Moreover, it provides a detailed comparative analysis of existing approaches under different categories.

Mathematical optimization applications in metabolic networks

Genome-scale metabolic models are increasingly becoming available for a variety of microorganisms. This has spurred the development of a wide array of computational tools, and in particular, mathematical optimization approaches, to assist in fundamental metabolic network analyses and redesign efforts. This review highlights a number of optimization-based frameworks developed towards addressing challenges in the analysis and engineering of metabolic networks. In particular, three major types of studies are covered here including exploring model predictions, correction and improvement of models of metabolism, and redesign of metabolic networks for the targeted overproduction of a desired compound. Overall, the methods reviewed in this paper highlight the diversity of queries, breadth of questions and complexity of redesigns that are amenable to mathematical optimization strategies.

The origin and ecological significance of multiple branches for histidine utilization in Pseudomonas aeruginosa PAO1

Pseudomonas proliferate in a wide spectrum of harsh and variable environments. In many of these environments, amino acids, such as histidine, are a valuable source of carbon, nitrogen and energy. Here, we demonstrate that the histidine uptake and utilization (hut) pathway of Pseudomonas aeruginosa PAO1 contains two branches from the intermediate formiminoglutamate to the product glutamate. Genetic analysis revealed that the four-step route is dispensable as long as the five-step route is present (and vice versa). Mutants with deletions of either the four-step (HutE) or five-step (HutFG) branches were competed against each other and the wild-type strain to test the hypothesis of ecological redundancy; that is, that the presence of two pathways confers no benefit beyond that delivered by the individual pathways. Fitness assays performed under several environmental conditions led us to reject this hypothesis; the four-step pathway can provide an advantage when histidine is the sole carbon source. An IclR-type regulator (HutR) was identified that regulates the four-step pathway. Comparison of sequenced genomes revealed that P.aeruginosa strains and P.fluorescens Pf-5 have branched hut pathways. Phylogenetic analyses suggests that the gene encoding formiminoglutamase (hutE) was acquired by horizontal gene transfer from a Ralstonia-like ancestor. Potential barriers to inter-species transfer of the hutRE module were explored by transferring it from P.aeruginosa PAO1 to P.fluorescens SBW25. Transfer of the operon conferred the ability to utilize histidine via the four-step pathway in a single step, but the fitness cost of acquiring this new operon was found to be environment dependent.

A CONSTRAINT-BASED STOICHIOMETRIC MODEL OF THE STEROIDOGENIC NETWORK OF ZEBRAFISH (DANIO RERIO)

The metabolic process of steroidogenesis exhibits a complex biochemical network topology as the activity of various steroidogenic enzymes control cholesterol metabolism to steroid hormone derivatives. In this paper, a stoichiometric reconstruction of a sub-set of 65 reactions from the zebrafish (Danio rerio) steroidogenic network is presented and simulated using uniform reaction constraints. The reconstruction defined a set of 65 enzyme catalyzed reactions and 37 exchange or transport reactions for steroid metabolites. The reconstructed reactions were inclusive of cholesterol and androgen/estrogen metabolism. Biased (statement of network objective function) and un-biased (no statement of objective function) analyses were applied to identify network properties dependent on reaction stoichiometry. Random sampling of flux distributions through the network identified highly-correlated reaction sets that corresponded to the catalysis of steroid metabolites of physiological relevance. Subsequently, optimal flux distributions through network pathways were determined for the production of the three steroidogenic metabolites of: 11-deoxycorticosterone, testosterone and 17β-estradiol. Furthermore, flux variability analyses revealed and confirmed optimal network fluxes through physiologically feasible pathways. The stoichiometric dependence of reactions was also confirmed by conducting deletions of reactions utilized for the optimal production of 17β-estradiol. This paper demonstrates the potential application of constraint-based reconstruction and simulation techniques in enabling the construction of deterministic and predictive physiological models. This acknowledgement is poignant considering the susceptibility of the steroidogenic network to environmental and anthropogenic stressors.

Decomposing flux distributions into elementary flux modes in genome-scale metabolic networks

MOTIVATION

Elementary flux mode (EFM) is a fundamental concept as well as a useful tool in metabolic pathway analysis. One important role of EFMs is that every flux distribution can be decomposed into a set of EFMs and a number of methods to study flux distributions originated from it. Yet finding such decompositions requires the complete set of EFMs, which is intractable in genome-scale metabolic networks due to combinatorial explosion.

RESULTS

In this article, we proposed an algorithm to decompose flux distributions into EFMs in genome-scale networks. It is an iterative scheme of a mixed integer linear program. Unlike previous optimization models to find pathways, any feasible solutions can become EFMs in our algorithm. This advantage enables the algorithm to approximate the EFM of largest contribution to an objective reaction in a flux distribution. Our algorithm is able to find EFMs of flux distributions with complex structures, closer to the realistic case in which a cell is subject to various constraints. A case of Escherichia coli growth in the Lysogeny broth (LB) medium containing various carbon sources was studied. Essential metabolites and their syntheses were located. Information on the contribution of each carbon source not obvious from the apparent flux distribution was also revealed. Our work further confirms the utility of finding EFMs by optimization models in genome-scale metabolic networks.

CONTACT

joshua.chan@connect.polyu.hk

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Pathway identification by network pruning in the metabolic network of Escherichia coli

MOTIVATION

All metabolic networks contain metabolites, such as ATP and NAD, known as currency metabolites, which take part in many reactions. These are often removed in the study of these networks, but no consensus exists on what actually constitutes a currency metabolite, and it is also unclear how these highly connected nodes contribute to the global structure of the network.

RESULTS

In this article, we analyse how the Escherichia coli metabolic network responds to pruning in the form of sequential removal of metabolites with highest degree. As expected this leads to network fragmentation, but the process by which it occurs suggests modularity and long-range correlations within the network. We find that the pruned networks contain longer paths than the random expectation, and that the paths that survive the pruning also exhibit a lower cost (number of involved metabolites) compared with random paths in the full metabolic network. Finally we confirm that paths detected by pruning overlap with known metabolic pathways. We conclude that pruning reveals functional pathways in metabolic networks, where currency metabolites may be seen as ingredients in a well-balanced soup in which main metabolic production lines are immersed.

CONTACT

gerlee@nbi.dk

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Computing the shortest elementary flux modes in genome-scale metabolic networks

MOTIVATION

Elementary flux modes (EFMs) represent a key concept to analyze metabolic networks from a pathway-oriented perspective. In spite of considerable work in this field, the computation of the full set of elementary flux modes in large-scale metabolic networks still constitutes a challenging issue due to its underlying combinatorial complexity.

RESULTS

In this article, we illustrate that the full set of EFMs can be enumerated in increasing order of number of reactions via integer linear programming. In this light, we present a novel procedure to efficiently determine the K-shortest EFMs in large-scale metabolic networks. Our method was applied to find the K-shortest EFMs that produce lysine in the genome-scale metabolic networks of Escherichia coli and Corynebacterium glutamicum. A detailed analysis of the biological significance of the K-shortest EFMs was conducted, finding that glucose catabolism, ammonium assimilation, lysine anabolism and cofactor balancing were correctly predicted. The work presented here represents an important step forward in the analysis and computation of EFMs for large-scale metabolic networks, where traditional methods fail for networks of even moderate size.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Metabolic pathfinding using RPAIR annotation

Metabolic databases contain information about thousands of small molecules and reactions, which can be represented as networks. In the context of metabolic reconstruction, pathways can be inferred by searching optimal paths in such networks. A recurrent problem is the presence of pool metabolites (e.g., water, energy carriers, and cofactors), which are connected to hundreds of reactions, thus establishing irrelevant shortcuts between nodes of the network. One solution to this problem relies on weighted networks to penalize highly connected compounds. A more refined solution takes the chemical structure of reactants into account in order to differentiate between side and main compounds of a reaction. Thanks to an intensive annotation effort at KEGG, decompositions of reactions into reactant pairs (RPAIR) categorized by their role (main, trans, cofac, ligase, and leave) are now available. The goal of this article is to evaluate the impact of RPAIR data on pathfinding in metabolic networks. To this end, we measure the impact of different parameters concerning the construction of the metabolic network: mapping of reactions and reactant pairs onto a graph, use of selected categories of reactant pairs, weighting schemes for compounds and reactions, removal of highly connected metabolites, and reaction directionality. In total, we tested 104 combinations of parameters and identified their optimal values for pathfinding on the basis of 55 reference pathways from three organisms. The best-performing metabolic network combines the biochemical knowledge encoded by KEGG RPAIR with a weighting scheme penalizing highly connected compounds. With this network, we could recover reference pathways from Escherichia coli with an average accuracy of 93% (32 pathways), from Saccharomyces cerevisiae with an average accuracy of 66% (11 pathways), and from humans with an average accuracy of 70% (12 pathways). Our pathfinding approach is available as part of the Network Analysis Tools.

Can sugars be produced from fatty acids? A test case for pathway analysis tools

MOTIVATION

In recent years, several methods have been proposed for determining metabolic pathways in an automated way based on network topology. The aim of this work is to analyse these methods by tackling a concrete example relevant in biochemistry. It concerns the question whether even-chain fatty acids, being the most important constituents of lipids, can be converted into sugars at steady state. It was proved five decades ago that this conversion using the Krebs cycle is impossible unless the enzymes of the glyoxylate shunt (or alternative bypasses) are present in the system. Using this example, we can compare the various methods in pathway analysis.

RESULTS

Elementary modes analysis (EMA) of a set of enzymes corresponding to the Krebs cycle, glycolysis and gluconeogenesis supports the scientific evidence showing that there is no pathway capable of converting acetyl-CoA to glucose at steady state. This conversion is possible after the addition of isocitrate lyase and malate synthase (forming the glyoxylate shunt) to the system. Dealing with the same example, we compare EMA with two tools based on graph theory available online, PathFinding and Pathway Hunter Tool. These automated network generating tools do not succeed in predicting the conversions known from experiment. They sometimes generate unbalanced paths and reveal problems identifying side metabolites that are not responsible for the carbon net flux. This shows that, for metabolic pathway analysis, it is important to consider the topology (including bimolecular reactions) and stoichiometry of metabolic systems, as is done in EMA.

A critical view of metabolic network adaptations

There has been considerable recent interest in deciphering the adaptive properties underlying the structure and function of metabolic networks. Various features of metabolic networks such as the global topology, distribution of fluxes, and mutational robustness, have been proposed to have adaptive significance and hence reflect design principles. However, whether evolutionary processes alternative to direct selection on the trait under investigation also play a role is often ignored and the selection pressures maintaining a given metabolic trait often remain speculative. Some systems-level traits might simply arise as by-products of selection on other traits or even through random genetic drift. Here, we ask which systems-level aspects of metabolism are likely to have adaptive utility and which could be better explained as by-products of other evolutionary forces. We conclude that the global topological characteristics of metabolic networks and their mutational robustness are unlikely to be directly shaped by natural selection. Conversely, models of optimal design revealed that various aspects of individual pathways and the behavior of the whole network show signs of adaptations, even though the exact selective forces often remain elusive. Comparative and experimental approaches, which so far have been relatively rarely employed, could help to distinguish between alternative adaptive scenarios.

The growing scope of applications of genome-scale metabolic reconstructions using Escherichia coli

The number and scope of methods developed to interrogate and use metabolic network reconstructions has significantly expanded over the past 15 years. In particular, Escherichia coli metabolic network reconstruction has reached the genome scale and been utilized to address a broad spectrum of basic and practical applications in five main categories: metabolic engineering, model-directed discovery, interpretations of phenotypic screens, analysis of network properties and studies of evolutionary processes. Spurred on by these accomplishments, the field is expected to move forward and further broaden the scope and content of network reconstructions, develop new and novel in silico analysis tools, and expand in adaptation to uses of proximal and distal causation in biology. Taken together, these efforts will solidify a mechanistic genotype-phenotype relationship for microbial metabolism.

A strategy to calculate the patterns of nutrient consumption by microorganisms applying a two-level optimisation principle to reconstructed metabolic networks

Bacterial responses to environmental changes rely on a complex network of biochemical reactions. The properties of the metabolic network determining these responses can be divided into two groups: the stoichiometric properties, given by the stoichiometry matrix, and the kinetic/thermodynamic properties, given by the rate equations of the reaction steps. The stoichiometry matrix represents the maximal metabolic capabilities of the organism, and the regulatory mechanisms based on the rate laws could be considered as being responsible for the administration of these capabilities. Post-genomic reconstruction of metabolic networks provides us with the stoichiometry matrix of particular strains of microorganisms, but the kinetic aspects of in vivo rate laws are still largely unknown. Therefore, the validity of predictions of cellular responses requiring detailed knowledge of the rate equations is difficult to assert. In this paper, we show that by applying optimisation criteria to the core stoichiometric network of the metabolism of Escherichia coli, and including information about reversibility/irreversibility only of the reaction steps, it is possible to calculate bacterial responses to growth media with different amounts of glucose and galactose. The target was the minimisation of the number of active reactions (subject to attaining a growth rate higher than a lower limit) and subsequent maximisation of the growth rate (subject to the number of active reactions being equal to the minimum previously calculated). Using this two-level target, we were able to obtain by calculation four fundamental behaviours found experimentally: inhibition of respiration at high glucose concentrations in aerobic conditions, turning on of respiration when glucose decreases, induction of galactose utilisation when the system is depleted of glucose and simultaneous use of glucose and galactose as carbon sources when both sugars are present in low concentrations. Preliminary results of the coarse pattern of sugar utilisation were also obtained with a genome-scale E. coli reconstructed network, yielding similar qualitative results.

Reconstruction and flux analysis of coupling between metabolic pathways of astrocytes and neurons: application to cerebral hypoxia

BACKGROUND

It is a daunting task to identify all the metabolic pathways of brain energy metabolism and develop a dynamic simulation environment that will cover a time scale ranging from seconds to hours. To simplify this task and make it more practicable, we undertook stoichiometric modeling of brain energy metabolism with the major aim of including the main interacting pathways in and between astrocytes and neurons.

MODEL

The constructed model includes central metabolism (glycolysis, pentose phosphate pathway, TCA cycle), lipid metabolism, reactive oxygen species (ROS) detoxification, amino acid metabolism (synthesis and catabolism), the well-known glutamate-glutamine cycle, other coupling reactions between astrocytes and neurons, and neurotransmitter metabolism. This is, to our knowledge, the most comprehensive attempt at stoichiometric modeling of brain metabolism to date in terms of its coverage of a wide range of metabolic pathways. We then attempted to model the basal physiological behaviour and hypoxic behaviour of the brain cells where astrocytes and neurons are tightly coupled.

RESULTS

The reconstructed stoichiometric reaction model included 217 reactions (184 internal, 33 exchange) and 216 metabolites (183 internal, 33 external) distributed in and between astrocytes and neurons. Flux balance analysis (FBA) techniques were applied to the reconstructed model to elucidate the underlying cellular principles of neuron-astrocyte coupling. Simulation of resting conditions under the constraints of maximization of glutamate/glutamine/GABA cycle fluxes between the two cell types with subsequent minimization of Euclidean norm of fluxes resulted in a flux distribution in accordance with literature-based findings. As a further validation of our model, the effect of oxygen deprivation (hypoxia) on fluxes was simulated using an FBA-derivative approach, known as minimization of metabolic adjustment (MOMA). The results show the power of the constructed model to simulate disease behaviour on the flux level, and its potential to analyze cellular metabolic behaviour in silico.

CONCLUSION

The predictive power of the constructed model for the key flux distributions, especially central carbon metabolism and glutamate-glutamine cycle fluxes, and its application to hypoxia is promising. The resultant acceptable predictions strengthen the power of such stoichiometric models in the analysis of mammalian cell metabolism.