Freeia: Robust optimal factories in metabolic reaction networks
|
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. In contrast to previous methods for finding factories, our approach does not use any user-set parameters that previously could exclude valid factories as solutions. Our robust approach for shortest factories solves a series of MILPs with a constraint on the number of allowed active hyperedges, while trying to maximize flux passed to the target.Methods
Freeia contains source code for robust 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 series of mixed-integer linear programs. 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).
Degeneracies in factories
We characterize the structure of factories for the first time. We show that all factories fall into one of three possible solution structures: s,t-trails, s,t-whirls, or s,t-eddies. We also show that whirls and eddies are degenerate and design an algorithm to find the shortest factory that is a non-degenerate s,t-trail.
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.
Publications
The methods implemented in Freeia are given in the following publication and noteworthy uses of Freeia should cite the following:- Spencer Krieger and John Kececioglu, “Computing robust optimal factories in metabolic reaction networks.” Submitted to RECOMB 2024.