Complementary elementary modes for fast and efficient analysis of metabolic networks

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.

Principal elementary mode analysis (PEMA)

Principal component analysis (PCA) has been widely applied in fluxomics to compress data into a few latent structures in order to simplify the identification of metabolic patterns. These latent structures lack a direct biological interpretation due to the intrinsic constraints associated with a PCA model. Here we introduce a new method that significantly improves the interpretability of the principal components with a direct link to metabolic pathways. This method, called principal elementary mode analysis (PEMA), establishes a bridge between a PCA-like model, aimed at explaining the maximum variance in flux data, and the set of elementary modes (EMs) of a metabolic network. It provides an easy way to identify metabolic patterns in large fluxomics datasets in terms of the simplest pathways of the organism metabolism. The results using a real metabolic model of Escherichia coli show the ability of PEMA to identify the EMs that generated the different simulated flux distributions. Actual flux data of E. coli and Pichia pastoris cultures confirm the results observed in the simulated study, providing a biologically meaningful model to explain flux data of both organisms in terms of the EM activation. The PEMA toolbox is freely available for non-commercial purposes on http://mseg.webs.upv.es.

Web application for genetic modification flux with database to estimate metabolic fluxes of genetic mutants

Computational analysis of metabolic fluxes is essential in understanding the structure and function of a metabolic network and in rationally designing genetically modified mutants for an engineering purpose. We had presented the genetic modification flux (GMF) that predicts the flux distribution of a broad range of genetically modified mutants. To enhance the feasibility and usability of GMF, we have developed a web application with a metabolic network database to predict a flux distribution of genetically modified mutants. One hundred and twelve data sets of Escherichia coli, Corynebacterium glutamicum, Saccharomyces cerevisiae, and Chinese hamster ovary were registered as standard models.