Odinn: Optimal minimum-hyperedge factories in metabolic networks with negative regulation
|
Overview
A factory in a metabolic network is a collection of reactions that produce a target substance starting from a set of source substances, properly taking into account the stoichiometries of intermediate metabolites in reactions. The reactions in the factory may form cycles, and effectively can proceed simultaneously. Our approach for finding minimum-hyperedge factories solves an MILP that minimizes the number of hyperedges, while ensuring flux constraints on intermediate metabolites are satisfied (either accumulation, where intermediate metabolites cannot be consumed, or conservation, where they also cannot be produced in excess). We also incorporate two orders of negative regulation: first order -- where a factory is invalid if it creates any metabolite that negatively regulates a reaction also in the factory, and second order -- where a factory is invalid if any molecule that negatively regulates a reaction in the factory can be created from the sources of the factory.Methods
Odinn contains source code for new algorithms for finding pathways in metabolic and signaling networks. Given a metabolic or signaling network as a hypergraph, set of sources (molecules available to the cell) and a set of targets (molecules we want the factory to produce), Odinn returns the factory producing the targets from the sources using the fewest reactions, while either conserving or not depleting intermediate metabolites. We formulate the problem of finding a minimum-hyperedge factory as a mixed-integer linear program. We incorporate two orders of negative regulation in two different ways, as described below. We also provide the datasets and the hypergraphs constructed from them, for all datasets referenced in our papers.Mixed-integer linear program
Our mixed-integer linear program (MILP) quickly finds the factory producing the targets using the fewest reactions. The MILP can be run under accumulation of intermediate metabolites (meaning they are not depleted), or conservation (meaning they are neither depleted nor accumulated).
Negative regulation
Each order of negative regulation is incorporated into our approach differently. First-order negative regulation, where a factory is invalid if it creates any metabolite that negatively regulates a reaction also in the factory, is handled directly as constraints within the MILP. Second-order negative regulation, where a factory is invalid if any molecule that negatively regulates a reaction in the factory can be created from the active sources of the factory, is handled by iteratively solving a series of MILPs, where constraints are added to exclude invalid factories at each iteration.
Performance
In comprehensive experiments on all instances from several metabolic and signaling networks, we found that our MILP-based approach is remarkably fast in practice, with a median running time of only a few seconds even including first-order and second-order negative regulation.
Publications
The methods implemented in Odinn are given in the following publication and noteworthy uses of Odinn should cite the following:- Spencer Krieger and John Kececioglu, “Computing optimal factories in metabolic networks with negative regulation.” Proceedings of the 28th International Conference on Intelligent Systems for Molecular Biology (ISMB), Bioinformatics 38, 2022. link
Source code
The MILP including negative regulation is available on GitHub.Videos
|
The following video was presented at ISMB 2022 and gives more detailed information on the algorithms implemented in Odinn
|
A shorter version was presented at SCS 2022:
|