Modes and cuts in metabolic networks: Complexity and algorithms

Finding Minimum Reaction Cuts of Metabolic Networks Under a Boolean Model Using Integer Programming and Feedback Vertex Sets

In this paper, the authors consider the problem of, given a metabolic network, a set of source compounds and a set of target compounds, finding a minimum size reaction cut, where a Boolean model is used as a model of metabolic networks. The problem has potential applications to measurement of structural robustness of metabolic networks and detection of drug targets. They develop an integer programming-based method for this optimization problem. In order to cope with cycles and reversible reactions, they further develop a novel integer programming (IP) formalization method using a feedback vertex set (FVS). When applied to an E. coli metabolic network consisting of Glycolysis/Glyconeogenesis, Citrate cycle and Pentose phosphate pathway obtained from KEGG database, the FVS-based method can find an optimal set of reactions to be inactivated much faster than a naive IP-based method and several times faster than a flux balance-based method. The authors also confirm that our proposed method works even for large networks and discuss the biological meaning of our results.

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.

Can the whole be less than the sum of its parts? Pathway analysis in genome-scale metabolic networks using elementary flux patterns

Elementary modes represent a valuable concept in the analysis of metabolic reaction networks. However, they can only be computed in medium-size systems, preventing application to genome-scale metabolic models. In consequence, the analysis is usually constrained to a specific part of the known metabolism, and the remaining system is modeled using abstractions like exchange fluxes and external species. As we show by the analysis of a model of the central metabolism of Escherichia coli that has been previously analyzed using elementary modes, the choice of these abstractions heavily impacts the pathways that are detected, and the results are biased by the knowledge of the metabolic capabilities of the network by the user. In order to circumvent these problems, we introduce the concept of elementary flux patterns, which explicitly takes into account possible steady-state fluxes through a genome-scale metabolic network when analyzing pathways through a subsystem. By being similar to elementary mode analysis, our concept now allows for the application of many elementary-mode-based tools to genome-scale metabolic networks. We present an algorithm to compute elementary flux patterns and analyze a model of the tricarboxylic acid cycle and adjacent reactions in E. coli. Thus, we detect several pathways that can be used as alternative routes to some central metabolic pathways. Finally, we give an outlook on further applications like the computation of minimal media, the development of knockout strategies, and the analysis of combined genome-scale networks.

An introduction to metabolic networks and their structural analysis

There has been a renewed interest for metabolism in the computational biology community, leading to an avalanche of papers coming from methodological network analysis as well as experimental and theoretical biology. This paper is meant to serve as an initial guide for both the biologists interested in formal approaches and the mathematicians or computer scientists wishing to inject more realism into their models. The paper is focused on the structural aspects of metabolism only. The literature is vast enough already, and the thread through it difficult to follow even for the more experienced worker in the field. We explain methods for acquiring data and reconstructing metabolic networks, and review the various models that have been used for their structural analysis. Several concepts such as modularity are introduced, as are the controversies that have beset the field these past few years, for instance, on whether metabolic networks are small-world or scale-free, and on which model better explains the evolution of metabolism. Clarifying the work that has been done also helps in identifying open questions and in proposing relevant future directions in the field, which we do along the paper and in the conclusion.