{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T15:39:14Z","timestamp":1762875554241,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Constrained minimal cut sets (cMCSs) have recently been introduced as a framework to enumerate minimal genetic intervention strategies for targeted optimization of metabolic networks. Two different algorithmic schemes (adapted Berge algorithm and binary integer programming) have been proposed to compute cMCSs from elementary modes. However, in their original formulation both algorithms are not fully comparable.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>Here we show that by a small extension to the integer program both methods become equivalent. Furthermore, based on well-known preprocessing procedures for integer programming we present efficient preprocessing steps which can be used for both algorithms. We then benchmark the numerical performance of the algorithms in several realistic medium-scale metabolic models. The benchmark calculations reveal (i) that these preprocessing steps can lead to an enormous speed-up under both algorithms, and (ii) that the adapted Berge algorithm outperforms the binary integer approach.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>Generally, both of our new implementations are by at least one order of magnitude faster than other currently available implementations.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-14-318","type":"journal-article","created":{"date-parts":[[2013,11,6]],"date-time":"2013-11-06T04:01:13Z","timestamp":1383710473000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Comparison and improvement of algorithms for computing minimal cut sets"],"prefix":"10.1186","volume":"14","author":[{"given":"Christian","family":"Jungreuthmayer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Govind","family":"Nair","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steffen","family":"Klamt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00fcrgen","family":"Zanghellini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,11,6]]},"reference":[{"issue":"6","key":"6856_CR1","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1038\/nchembio.970","volume":"8","author":"JW Lee","year":"2012","unstructured":"Lee JW, Na D, Park JM, Lee J, Choi S, Lee SY: Systems metabolic engineering of microorganisms for natural and non-natural chemicals. Nat Chem Biol. 2012, 8 (6): 536-546. 10.1038\/nchembio.970.","journal-title":"Nat Chem Biol"},{"issue":"5","key":"6856_CR2","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1016\/j.ymben.2011.06.008","volume":"13","author":"P Xu","year":"2011","unstructured":"Xu P, Ranganathan S, Fowler ZL, Maranas CD, Koffas MA: Genome-scale metabolic network modeling results in minimal interventions that cooperatively force carbon flux towards malonyl-CoA. Metab Eng. 2011, 13 (5): 578-587. 10.1016\/j.ymben.2011.06.008.","journal-title":"Metab Eng"},{"issue":"6","key":"6856_CR3","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1016\/j.ymben.2012.09.005","volume":"14","author":"AR Zomorrodi","year":"2012","unstructured":"Zomorrodi AR, Suthers PF, Ranganathan S, Maranas CD: Mathematical optimization applications in metabolic networks. Metab Eng. 2012, 14 (6): 672-686. 10.1016\/j.ymben.2012.09.005.","journal-title":"Metab Eng"},{"key":"6856_CR4","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1186\/1752-0509-4-53","volume":"4","author":"J Kim","year":"2010","unstructured":"Kim J, Reed J: OptORF: Optimal metabolic and regulatory perturbations for metabolic engineering of microbial strains. BMC Syst Biol. 2010, 4: 53-10.1186\/1752-0509-4-53.","journal-title":"BMC Syst Biol"},{"issue":"10","key":"6856_CR5","doi-asserted-by":"publisher","first-page":"3097","DOI":"10.1128\/AEM.00115-10","volume":"76","author":"HS Choi","year":"2010","unstructured":"Choi HS, Lee SY, Kim TY, Woo HM: In Silico identification of gene amplification targets for improvement of lycopene production. Appl Environ Microbiolo. 2010, 76 (10): 3097-3105. 10.1128\/AEM.00115-10.","journal-title":"Appl Environ Microbiolo"},{"issue":"4","key":"6856_CR6","doi-asserted-by":"publisher","first-page":"e1000744","DOI":"10.1371\/journal.pcbi.1000744","volume":"6","author":"S Ranganathan","year":"2010","unstructured":"Ranganathan S, Suthers PF, Maranas CD: OptForce: An optimization procedure for identifying all genetic manipulations leading to targeted overproductions. PLoS Comput Biol. 2010, 6 (4): e1000744-10.1371\/journal.pcbi.1000744.","journal-title":"PLoS Comput Biol"},{"issue":"11","key":"6856_CR7","doi-asserted-by":"publisher","first-page":"2367","DOI":"10.1101\/gr.2872004","volume":"14","author":"P Pharkya","year":"2004","unstructured":"Pharkya P, Burgard AP, Maranas CD: OptStrain: A computational framework for redesign of microbial production systems. Genome Res. 2004, 14 (11): 2367-2376. 10.1101\/gr.2872004.","journal-title":"Genome Res"},{"issue":"6","key":"6856_CR8","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1002\/bit.10803","volume":"84","author":"AP Burgard","year":"2003","unstructured":"Burgard AP, Pharkya P, Maranas CD: Optknock: A bilevel programming framework for identifying gene knockout strategies for microbial strain optimization. Biotechnol Bioeng. 2003, 84 (6): 647-657. 10.1002\/bit.10803.","journal-title":"Biotechnol Bioeng"},{"issue":"23","key":"6856_CR9","doi-asserted-by":"publisher","first-page":"15112","DOI":"10.1073\/pnas.232349399","volume":"99","author":"D Segr\u00e8","year":"2002","unstructured":"Segr\u00e8 D, Vitkup D, Church GM: Analysis of optimality in natural and perturbed metabolic networks. Proc Natl Acad Sci. 2002, 99 (23): 15112-15117. 10.1073\/pnas.232349399.","journal-title":"Proc Natl Acad Sci"},{"key":"6856_CR10","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1186\/1752-0509-6-103","volume":"6","author":"C Jungreuthmayer","year":"2012","unstructured":"Jungreuthmayer C, Zanghellini J: Designing optimal cell factories: Integer programing couples elementary mode analysis with regulation. BMC Syst Biol. 2012, 6: 103-10.1186\/1752-0509-6-103.","journal-title":"BMC Syst Biol"},{"issue":"2","key":"6856_CR11","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.ymben.2010.12.004","volume":"13","author":"O H\u00e4dicke","year":"2011","unstructured":"H\u00e4dicke O, Klamt S: Computing complex metabolic intervention strategies using constrained minimal cut sets. Metab Eng. 2011, 13 (2): 204-213. 10.1016\/j.ymben.2010.12.004. http:\/\/www.ncbi.nlm.nih.gov\/pubmed\/21147248,","journal-title":"Metab Eng"},{"issue":"3","key":"6856_CR12","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1038\/73786","volume":"18","author":"S Schuster","year":"2000","unstructured":"Schuster S, Fell DA, Dandekar T: A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic networks. Nat Biotech. 2000, 18 (3): 326-332. 10.1038\/73786. http:\/\/dx.doi.org\/10.1038\/73786,","journal-title":"Nat Biotech"},{"issue":"2","key":"6856_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0167-7799(98)01290-6","volume":"17","author":"S Schuster","year":"1999","unstructured":"Schuster S, Dandekar T, Fell DA: Detection of elementary flux modes in biochemical networks: a promising tool for pathway analysis and metabolic engineering. Trends Biotechnol. 1999, 17 (2): 53-60. 10.1016\/S0167-7799(98)01290-6. http:\/\/www.ncbi.nlm.nih.gov\/pubmed\/10087604,","journal-title":"Trends Biotechnol"},{"issue":"2","key":"6856_CR14","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.ymben.2011.01.003","volume":"13","author":"J Becker","year":"2011","unstructured":"Becker J, Zelder O, H\u00e4fner S, Schr\u00f6der H, Wittmann C: From zero to hero-design-based systems metabolic engineering of Corynebacterium glutamicum for L-lysine production. Metab Eng. 2011, 13 (2): 159-168. 10.1016\/j.ymben.2011.01.003.","journal-title":"Metab Eng"},{"issue":"14","key":"6856_CR15","doi-asserted-by":"publisher","first-page":"4894","DOI":"10.1128\/AEM.00382-11","volume":"77","author":"CT Trinh","year":"2011","unstructured":"Trinh CT, Li J, Blanch HW, Clark DS: Redesigning Escherichia coli metabolism for Anaerobic production of Isobutanol. Appl Environ Microbiol. 2011, 77 (14): 4894-4904. 10.1128\/AEM.00382-11.","journal-title":"Appl Environ Microbiol"},{"issue":"12","key":"6856_CR16","doi-asserted-by":"publisher","first-page":"3634","DOI":"10.1128\/AEM.02708-07","volume":"74","author":"CT Trinh","year":"2008","unstructured":"Trinh CT, Unrean P, Srienc F: Minimal Escherichia coli cell for the most efficient production of ethanol from Hexoses and Pentoses. Appl Environ Microbiol. 2008, 74 (12): 3634-3643. 10.1128\/AEM.02708-07. http:\/\/aem.asm.org\/content\/74\/12\/3634.abstract,","journal-title":"Appl Environ Microbiol"},{"issue":"2","key":"6856_CR17","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.ymben.2009.11.002","volume":"12","author":"P Unrean","year":"2010","unstructured":"Unrean P, Trinh CT, Srienc F: Rational design and construction of an efficient E. coli for production of diapolycopendioic acid. Metab Eng. 2010, 12 (2): 112-122. 10.1016\/j.ymben.2009.11.002.","journal-title":"Metab Eng"},{"key":"6856_CR18","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S1004-9541(08)60052-X","volume":"16","author":"X Xu","year":"2008","unstructured":"Xu X, Cao L, Chen X: Elementary flux mode analysis for optimized ethanol yield in anaerobic fermentation of glucose with saccharomyces cerevisiae. Chin J Chem Eng. 2008, 16: 135-142. 10.1016\/S1004-9541(08)60052-X.","journal-title":"Chin J Chem Eng"},{"key":"6856_CR19","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.ymben.2011.11.002","volume":"14","author":"H Driouch","year":"2012","unstructured":"Driouch H, Melzer G, Wittmann C: Integration of in vivo and in silico metabolic fluxes for improvement of recombinant protein production. Metab Eng. 2012, 14: 47-58. 10.1016\/j.ymben.2011.11.002.","journal-title":"Metab Eng"},{"issue":"9","key":"6856_CR20","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1002\/biot.201200269","volume":"8","author":"J Zanghellini","year":"2013","unstructured":"Zanghellini J, Ruckerbauer DE, Hanscho M, Jungreuthmayer C: Elementary flux modes in a nutshell: properties, calculation and applications. Biotechnol J. 2013, 8 (9): 1009-1016. 10.1002\/biot.201200269.","journal-title":"Biotechnol J"},{"issue":"5","key":"6856_CR21","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1007\/s00253-008-1770-1","volume":"81","author":"C Trinh","year":"2009","unstructured":"Trinh C, Wlaschin A, Srienc F: Elementary mode analysis: a useful metabolic pathway analysis tool for characterizing cellular metabolism. Appl Microbiol Biotechnol. 2009, 81 (5): 813-826. 10.1007\/s00253-008-1770-1.","journal-title":"Appl Microbiol Biotechnol"},{"key":"6856_CR22","volume-title":"Hypergraphs: Combinatorics of Finite Sets","author":"C Berge","year":"1989","unstructured":"Berge C: Hypergraphs: Combinatorics of Finite Sets. 1989, (North-Holland mathematical library: Volume 45.) Amsterdam: Elsevier Science Publishers"},{"issue":"3","key":"6856_CR23","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1089\/cmb.2007.0229","volume":"15","author":"UU Haus","year":"2008","unstructured":"Haus UU, Klamt S, Stephen T: Computing knock-out strategies in metabolic networks. J Comput Biol. 2008, 15 (3): 259-268. 10.1089\/cmb.2007.0229.","journal-title":"J Comput Biol"},{"key":"6856_CR24","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.biosystems.2013.04.002","volume":"113","author":"C Jungreuthmayer","year":"2013","unstructured":"Jungreuthmayer C, Ruckerbauer DE, Zanghellini J: regEfmtool: Speeding up elementary flux mode calculation using transcriptional regulatory rules in the form of three-state logic. Biosystems. 2013, 113: 37-39. 10.1016\/j.biosystems.2013.04.002.","journal-title":"Biosystems"},{"issue":"6-7","key":"6856_CR25","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/j.parco.2011.04.002","volume":"37","author":"D Jevremovi\u0107","year":"2011","unstructured":"Jevremovi\u0107 D, Trinh CT, Srienc F, Sosa CP, Boley D: Parallelization of Nullspace algorithm for the computation of metabolic pathways. Parallel Comput. 2011, 37 (6-7): 261-278. 10.1016\/j.parco.2011.04.002.","journal-title":"Parallel Comput"},{"issue":"19","key":"6856_CR26","doi-asserted-by":"publisher","first-page":"2229","DOI":"10.1093\/bioinformatics\/btn401","volume":"24","author":"M Terzer","year":"2008","unstructured":"Terzer M, Stelling J: Large-scale computation of elementary flux modes with bit pattern trees. Bioinformatics. 2008, 24 (19): 2229-2235. 10.1093\/bioinformatics\/btn401.","journal-title":"Bioinformatics"},{"issue":"15","key":"6856_CR27","doi-asserted-by":"publisher","first-page":"1930","DOI":"10.1093\/bioinformatics\/btl267","volume":"22","author":"Av Kamp","year":"2006","unstructured":"Kamp Av, Schuster S: Metatool 5.0: fast and flexible elementary modes analysis. Bioinformatics. 2006, 22 (15): 1930-1931. 10.1093\/bioinformatics\/btl267.","journal-title":"Bioinformatics"},{"issue":"11","key":"6856_CR28","doi-asserted-by":"publisher","first-page":"2035","DOI":"10.1016\/j.dam.2007.04.017","volume":"156","author":"T Eiter","year":"2008","unstructured":"Eiter T, Makino K, Gottlob G: Computational aspects of monotone dualization: A brief survey. Discrete Appl Math. 2008, 156 (11): 2035-2049. 10.1016\/j.dam.2007.04.017.","journal-title":"Discrete Appl Math"},{"key":"6856_CR29","volume-title":"Applied Integer Programming: Modeling and Solution","author":"DS Chen","year":"2010","unstructured":"Chen DS, Batson RG, Dang Y: Applied Integer Programming: Modeling and Solution. 2010, Hoboken: John Wiley & Sons, Inc."},{"key":"6856_CR30","first-page":"56","volume-title":"EcoSal-Escherichia coli and Salmonella: Cellular and Molecular Biology","author":"JD Orth","year":"2009","unstructured":"Orth JD, Fleming RMT, Palsson B\u00d8: Reconstruction and use of microbial metabolic networks: the core escherichia coli metabolic model as an educational guide. EcoSal-Escherichia coli and Salmonella: Cellular and Molecular Biology. Edited by: B\u00f6ck A, Curtiss IIIR, Kaper JB, Karp PD, Neidhardt FC, Nystr\u00f6m T, Slauch JM, Squires CL, Ussery D. 2009, Washington: ASM Press, 56-99. chapter 10.2.1"},{"issue":"2","key":"6856_CR31","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.mib.2008.02.007","volume":"11","author":"J Deutscher","year":"2008","unstructured":"Deutscher J: The mechanisms of carbon catabolite repression in bacteria. Curr Opin Microbiol. 2008, 11 (2): 87-93. 10.1016\/j.mib.2008.02.007.","journal-title":"Curr Opin Microbiol"},{"key":"6856_CR32","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1186\/1752-0509-1-2","volume":"1","author":"S Klamt","year":"2007","unstructured":"Klamt S, Saez-Rodriguez J, Gilles E: Structural and functional analysis of cellular networks with CellNetAnalyzer. BMC Syst Biol. 2007, 1: 2-10.1186\/1752-0509-1-2.","journal-title":"BMC Syst Biol"},{"issue":"4","key":"6856_CR33","doi-asserted-by":"publisher","first-page":"1083","DOI":"10.1007\/s00253-012-4197-7","volume":"95","author":"CT Trinh","year":"2012","unstructured":"Trinh CT: Elucidating and reprogramming Escherichia coli metabolisms for obligate anaerobic n-butanol and isobutanol production. Appl Microbiol Biotechnol. 2012, 95 (4): 1083-1094. 10.1007\/s00253-012-4197-7.","journal-title":"Appl Microbiol Biotechnol"},{"key":"6856_CR34","volume-title":"arXiv:1102.3813","author":"K Murakami","year":"2011","unstructured":"Murakami K, Uno T: Efficient algorithms for dualizing large-scale hypergraphs. arXiv:1102.3813. 2011, http:\/\/arxiv.org\/abs\/1102.3813,"},{"issue":"4","key":"6856_CR35","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1287\/ijoc.6.4.445","volume":"6","author":"MWP Savelsbergh","year":"1994","unstructured":"Savelsbergh MWP: Preprocessing and probing techniques for mixed integer programming problems. ORSA J Comput. 1994, 6 (4): 445-454. 10.1287\/ijoc.6.4.445.","journal-title":"ORSA J Comput"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-14-318.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T20:01:05Z","timestamp":1630612865000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-14-318"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,6]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["6856"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-14-318","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2013,11,6]]},"assertion":[{"value":"18 January 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2013","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2013","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"318"}}