{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:04:11Z","timestamp":1773270251121,"version":"3.50.1"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T00:00:00Z","timestamp":1656288000000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["CCF-1617192"],"award-info":[{"award-number":["CCF-1617192"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["IIS-2041613"],"award-info":[{"award-number":["IIS-2041613"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,6,24]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>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.<\/jats:p><\/jats:sec><jats:sec><jats:title>Methods<\/jats:title><jats:p>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.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>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.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>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 http:\/\/odinn.cs.arizona.edu.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btac231","type":"journal-article","created":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T11:10:15Z","timestamp":1649934615000},"page":"i369-i377","source":"Crossref","is-referenced-by-count":5,"title":["Computing optimal factories in metabolic networks with negative regulation"],"prefix":"10.1093","volume":"38","author":[{"given":"Spencer","family":"Krieger","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Arizona , Tucson, AZ 85721, USA"}]},{"given":"John","family":"Kececioglu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Arizona , Tucson, AZ 85721, USA"}]}],"member":"286","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"2474","DOI":"10.1093\/bioinformatics\/bts423","article-title":"Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks","volume":"28","author":"Acu\u00f1a","year":"2012","journal-title":"Bioinformatics"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1186\/s13015-016-0087-3","article-title":"Enumeration of minimal stoichiometric precursor sets in metabolic networks","volume":"11","author":"Andrade","year":"2016","journal-title":"Algorithms Mol. Biol"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1186\/1752-0509-6-10","article-title":"Enumerating metabolic pathways for the production of heterologous target chemicals in chassis organisms","volume":"6","author":"Carbonell","year":"2012","journal-title":"BMC Syst. Biol"},{"key":"2023041407541548700_","first-page":"233","author":"Cottret","year":"2008"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"W495","DOI":"10.1093\/nar\/gky301","article-title":"MetExplore: collaborative edition and exploration of metabolic networks","volume":"46","author":"Cottret","year":"2018","journal-title":"Nucleic Acids Res"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"3158","DOI":"10.1093\/bioinformatics\/btp564","article-title":"Computing the shortest elementary flux modes in genome-scale metabolic networks","volume":"25","author":"de Figueiredo","year":"2009","journal-title":"Bioinformatics"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1038\/nbt.1666","article-title":"The BioPAX community standard for pathway data sharing","volume":"28","author":"Demir","year":"2010","journal-title":"Nat. Biotechnol"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"e1007384","DOI":"10.1371\/journal.pcbi.1007384","article-title":"Hypergraph-based connectivity measures for signaling pathway topologies","volume":"15","author":"Franzese","year":"2019","journal-title":"PLoS Comput. Biol"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","article-title":"Directed hypergraphs and applications","volume":"42","author":"Gallo","year":"1993","journal-title":"Discrete Appl. Math"},{"key":"2023041407541548700_","volume-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"2023041407541548700_","author":"Italiano","year":"1989"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"D428","DOI":"10.1093\/nar\/gki072","article-title":"Reactome: a knowledgebase of biological pathways","volume":"33","author":"Joshi-Tope","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1186\/1752-0509-6-103","article-title":"Designing optimal cell factories: integer programming couples elementary mode analysis with regulation","volume":"6","author":"Jungreuthmayer","year":"2012","journal-title":"BMC Syst. Biol"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"e0129840","DOI":"10.1371\/journal.pone.0129840","article-title":"Avoiding the enumeration of infeasible elementary flux modes by including transcriptional regulatory rules in the enumeration process saves computational costs","volume":"10","author":"Jungreuthmayer","year":"2015","journal-title":"PLoS One"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"e1000385","DOI":"10.1371\/journal.pcbi.1000385","article-title":"Hypergraphs and cellular networks","volume":"5","author":"Klamt","year":"2009","journal-title":"PLoS Comput. Biol"},{"key":"2023041407541548700_","first-page":"1","author":"Krieger","year":"2021"},{"key":"2023041407541548700_","author":"Krieger","year":"2022"},{"key":"2023041407541548700_","author":"Krieger","year":"2022"},{"key":"2023041407541548700_","author":"Krieger","year":"2022"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2017\/5987082","article-title":"Omega-3 polyunsaturated fatty acids in critical illness: anti-inflammatory, proresolving, or both?","volume":"2017","author":"Molfino","year":"2017","journal-title":"Oxid. Med. Cell. Longev"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1038\/msb.2009.77","article-title":"Applications of genome-scale metabolic reconstructions","volume":"5","author":"Oberhardt","year":"2009","journal-title":"Mol. Syst. Biol"},{"key":"2023041407541548700_","first-page":"249","author":"Ritz","year":"2014"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1016\/j.tibtech.2014.04.007","article-title":"Signaling hypergraphs","volume":"32","author":"Ritz","year":"2014","journal-title":"Trends Biotechnol"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"1042","DOI":"10.1109\/TCBB.2015.2459681","article-title":"Pathway analysis with signaling hypergraphs","volume":"14","author":"Ritz","year":"2017","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"1151","DOI":"10.1109\/TCBB.2019.2937033","article-title":"Modeling cell communication with time-dependent signaling hypergraphs","volume":"18","author":"Schwob","year":"2021","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1038\/nbt1196","article-title":"Modeling cellular machinery through biological network comparison","volume":"24","author":"Sharan","year":"2006","journal-title":"Nat. Biotechnol"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"986","DOI":"10.1016\/j.cell.2011.02.016","article-title":"Interactome networks and human disease","volume":"144","author":"Vidal","year":"2011","journal-title":"Cell"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1002\/biot.201200269","article-title":"Elementary flux modes in a nutshell: properties, calculation and applications","volume":"8","author":"Zanghellini","year":"2013","journal-title":"Biotechnol. J"},{"key":"2023041407541548700_","doi-asserted-by":"crossref","first-page":"e1003726","DOI":"10.1371\/journal.pcbi.1003726","article-title":"A novel nutritional predictor links microbial fastidiousness with lowered ubiquity, growth rate, and cooperativeness","volume":"10","author":"Zarecki","year":"2014","journal-title":"PLoS Comput. Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i369\/49886935\/btac231.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i369\/49886935\/btac231.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T00:28:28Z","timestamp":1700440108000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/Supplement_1\/i369\/6617500"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,24]]},"references-count":29,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2022,6,24]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac231","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,7,1]]},"published":{"date-parts":[[2022,6,24]]}}}