TY - JOUR
T1 - Computing optimal factories in metabolic networks with negative regulation
AU - Krieger, Spencer
AU - Kececioglu, John
N1 - Funding Information:
This research was supported by the US National Science Foundation through grants CCF-1617192 and IIS-2041613 to J.K.
Publisher Copyright:
© 2022 The Author(s) 2022. Published by Oxford University Press.
PY - 2022/7/1
Y1 - 2022/7/1
N2 - 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. Methods: 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. Results: 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.
AB - 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. Methods: 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. Results: 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.
UR - http://www.scopus.com/inward/record.url?scp=85132957102&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85132957102&partnerID=8YFLogxK
U2 - 10.1093/bioinformatics/btac231
DO - 10.1093/bioinformatics/btac231
M3 - Article
C2 - 35758789
AN - SCOPUS:85132957102
SN - 1367-4803
VL - 38
SP - I369-I377
JO - Bioinformatics
JF - Bioinformatics
ER -