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 -