skip to main content

Title: Computing optimal factories in metabolic networks with negative regulation
Abstract Motivation

A factory in a metabolic network specifies how to produce target molecules from source compounds through biochemical reactions, properly accounting for reaction stoichiometry to conserve or not deplete intermediate metabolites. While finding factories is a fundamental problem in systems biology, available methods do not consider the number of reactions used, nor address negative regulation.


We introduce the new problem of finding optimal factories that use the fewest reactions, for the first time incorporating both first- and second-order negative regulation. We model this problem with directed hypergraphs, prove it is NP-complete, solve it via mixed-integer linear programming, and accommodate second-order negative regulation by an iterative approach that generates next-best factories.


This optimization-based approach is remarkably fast in practice, typically finding optimal factories in a few seconds, even for metabolic networks involving tens of thousands of reactions and metabolites, as demonstrated through comprehensive experiments across all instances from standard reaction databases.

Availability and implementation

Source code for an implementation of our new method for optimal factories with negative regulation in a new tool called Odinn, together with all datasets, is available free for non-commercial use at

more » « less
Award ID(s):
Author(s) / Creator(s):
Publisher / Repository:
Oxford University Press
Date Published:
Journal Name:
Medium: X Size: p. i369-i377
["p. i369-i377"]
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Background

    The topology of metabolic networks is both well-studied and remarkably well-conserved across many species. The regulation of these networks, however, is much more poorly characterized, though it is known to be divergent across organisms—two characteristics that make it difficult to model metabolic networks accurately. While many computational methods have been built to unravel transcriptional regulation, there have been few approaches developed for systems-scale analysis and study of metabolic regulation. Here, we present a stepwise machine learning framework that applies established algorithms to identify regulatory interactions in metabolic systems based on metabolic data: stepwise classification of unknown regulation, or SCOUR.


    We evaluated our framework on both noiseless and noisy data, using several models of varying sizes and topologies to show that our approach is generalizable. We found that, when testing on data under the most realistic conditions (low sampling frequency and high noise), SCOUR could identify reaction fluxes controlled only by the concentration of a single metabolite (its primary substrate) with high accuracy. The positive predictive value (PPV) for identifying reactions controlled by the concentration of two metabolites ranged from 32 to 88% for noiseless data, 9.2 to 49% for either low sampling frequency/low noise or high sampling frequency/high noise data, and 6.6–27% for low sampling frequency/high noise data, with results typically sufficiently high for lab validation to be a practical endeavor. While the PPVs for reactions controlled by three metabolites were lower, they were still in most cases significantly better than random classification.


    SCOUR uses a novel approach to synthetically generate the training data needed to identify regulators of reaction fluxes in a given metabolic system, enabling metabolomics and fluxomics data to be leveraged for regulatory structure inference. By identifying and triaging the most likely candidate regulatory interactions, SCOUR can drastically reduce the amount of time needed to identify and experimentally validate metabolic regulatory interactions. As high-throughput experimental methods for testing these interactions are further developed, SCOUR will provide critical impact in the development of predictive metabolic models in new organisms and pathways.

    more » « less
  2. Signaling and metabolic pathways, which consist of a series of reactions producing target molecules from source compounds, are cornerstones of cellular biology. The cellular reaction networks containing such pathways can be precisely modeled by directed hypergraphs, where each reaction corresponds to a hyperedge, directed from its set of reactants to its set of products. Given such a network represented by a directed hypergraph, inferring the most likely set of reactions that produce a given target from a given set of sources corresponds to finding a shortest hyperpath, which is NP-complete. The best methods currently available for shortest hyperpaths either offer no guarantee of optimality, or exclude hyperpaths containing cycles even though cycles are abundant in real biological pathways. We derive a novel graph-theoretic characterization of hyperpaths, leveraged in a new formulation of the general shortest hyperpath problem as an integer linear program that for the first time handles hyperpaths containing cycles, and present a novel cutting-plane algorithm that can solve this integer program to optimality in practice. This represents a major advance over the best prior exact algorithm, which was limited to acyclic hyperpaths (and hence fails to find a solution for the many biological instances where all hyperpaths are in fact cyclic). In comprehensive experiments over thousands of instances from the standard NCI-PID and Reactome databases, we demonstrate that our cutting-plane algorithm quickly finds an optimal hyperpath, with a median running-time of under ten seconds and a maximum time of around thirty minutes, even on large instances with many thousands of reactions. Source code implementing our cutting-plane algorithm for shortest hyperpaths in a new tool called Mmunin is available free for research use at 
    more » « less
  3. Microbes, such as bacteria, can be described, at one level, as small, self-sustaining chemical factories. Based on the species, strain, and even the environment, bacteria can be useful, neutral or pathogenic to human life, so it is increasingly important that we be able to characterize them at the molecular level with chemical specificity and spatial and temporal resolution in order to understand their behavior. Bacterial metabolism involves a large number of internal and external electron transfer processes, so it is logical that electrochemical techniques have been employed to investigate these bacterial metabolites. In this mini-review, we focus on electrochemical and spectroelectrochemical methods that have been developed and used specifically to chemically characterize bacteria and their behavior. First, we discuss the latest mechanistic insights and current understanding of microbial electron transfer, including both direct and mediated electron transfer. Second, we summarize progress on approaches to spatiotemporal characterization of secreted factors, including both metabolites and signaling molecules, which can be used to discern how natural or external factors can alter metabolic states of bacterial cells and change either their individual or collective behavior. Finally, we address in situ methods of single-cell characterization, which can uncover how heterogeneity in cell behavior is reflected in the behavior and properties of collections of bacteria, e.g. bacterial communities. Recent advances in (spectro)electrochemical characterization of bacteria have yielded important new insights both at the ensemble and the single-entity levels, which are furthering our understanding of bacterial behavior. These insights, in turn, promise to benefit applications ranging from biosensors to the use of bacteria in bacteria-based bioenergy generation and storage. 
    more » « less
  4. Abstract Summary

    Although advances in untargeted metabolomics have made it possible to gather data on thousands of cellular metabolites in parallel, identification of novel metabolites from these datasets remains challenging. To address this need, Metabolic in silico Network Expansions (MINEs) were developed. A MINE is an expansion of known biochemistry which can be used as a list of potential structures for unannotated metabolomics peaks. Here, we present MINE 2.0, which utilizes a new set of biochemical transformation rules that covers 93% of MetaCyc reactions (compared to 25% in MINE 1.0). This results in a 17-fold increase in database size and a 40% increase in MINE database compounds matching unannotated peaks from an untargeted metabolomics dataset. MINE 2.0 is thus a significant improvement to this community resource.

    Availability and implementation

    The MINE 2.0 website can be accessed at The MINE 2.0 web API documentation can be accessed at The data and code underlying this article are available in the MINE-2.0-Paper repository at MINE 2.0 source code can be accessed at (MINE construction), (backend web API) and (web app).

    Supplementary information

    Supplementary data are available at Bioinformatics online.

    more » « less
  5. Abstract STUDY QUESTION

    Is the combined use of fluorescence lifetime imaging microscopy (FLIM)-based metabolic imaging and second harmonic generation (SHG) spindle imaging a feasible and safe approach for noninvasive embryo assessment?


    Metabolic imaging can sensitively detect meaningful metabolic changes in embryos, SHG produces high-quality images of spindles and the methods do not significantly impair embryo viability.


    Proper metabolism is essential for embryo viability. Metabolic imaging is a well-tested method for measuring metabolism of cells and tissues, but it is unclear if it is sensitive enough and safe enough for use in embryo assessment.


    This study consisted of time-course experiments and control versus treatment experiments. We monitored the metabolism of 25 mouse oocytes with a noninvasive metabolic imaging system while exposing them to oxamate (cytoplasmic lactate dehydrogenase inhibitor) and rotenone (mitochondrial oxidative phosphorylation inhibitor) in series. Mouse embryos (n = 39) were measured every 2 h from the one-cell stage to blastocyst in order to characterize metabolic changes occurring during pre-implantation development. To assess the safety of FLIM illumination, n = 144 illuminated embryos were implanted into n = 12 mice, and n = 108 nonilluminated embryos were implanted into n = 9 mice.


    Experiments were performed in mouse embryos and oocytes. Samples were monitored with noninvasive, FLIM-based metabolic imaging of nicotinamide adenine dinucleotide (NADH) and flavin adenine dinucleotide (FAD) autofluorescence. Between NADH cytoplasm, NADH mitochondria and FAD mitochondria, a single metabolic measurement produces up to 12 quantitative parameters for characterizing the metabolic state of an embryo. For safety experiments, live birth rates and pup weights (mean ± SEM) were used as endpoints. For all test conditions, the level of significance was set at P < 0.05.


    Measured FLIM parameters were highly sensitive to metabolic changes due to both metabolic perturbations and embryo development. For oocytes, metabolic parameter values were compared before and after exposure to oxamate and rotenone. The metabolic measurements provided a basis for complete separation of the data sets. For embryos, metabolic parameter values were compared between the first division and morula stages, morula and blastocyst and first division and blastocyst. The metabolic measurements again completely separated the data sets. Exposure of embryos to excessive illumination dosages (24 measurements) had no significant effect on live birth rate (5.1 ± 0.94 pups/mouse for illuminated group; 5.7 ± 1.74 pups/mouse for control group) or pup weights (1.88 ± 0.10 g for illuminated group; 1.89 ± 0.11 g for control group).


    The study was performed using a mouse model, so conclusions concerning sensitivity and safety may not generalize to human embryos. A limitation of the live birth data is also that although cages were routinely monitored, we could not preclude that some runt pups may have been eaten.


    Promising proof-of-concept results demonstrate that FLIM with SHG provide detailed biological information that may be valuable for the assessment of embryo and oocyte quality. Live birth experiments support the method’s safety, arguing for further studies of the clinical utility of these techniques.


    Supported by the Blavatnik Biomedical Accelerator Grant at Harvard University and by the Harvard Catalyst/The Harvard Clinical and Translational Science Center (National Institutes of Health Award UL1 TR001102), by NSF grants DMR-0820484 and PFI-TT-1827309 and by NIH grant R01HD092550-01. T.S. was supported by a National Science Foundation Postdoctoral Research Fellowship in Biology grant (1308878). S.F. and S.A. were supported by NSF MRSEC DMR-1420382. Becker and Hickl GmbH sponsored the research with the loaning of equipment for FLIM. T.S. and D.N. are cofounders and shareholders of LuminOva, Inc., and co-hold patents (US20150346100A1 and US20170039415A1) for metabolic imaging methods. D.S. is on the scientific advisory board for Cooper Surgical and has stock options with LuminOva, Inc.

    more » « less