{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:05:45Z","timestamp":1773270345652,"version":"3.50.1"},"reference-count":12,"publisher":"Oxford University Press (OUP)","issue":"19","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: In the context of studying whole metabolic networks and their interaction with the environment, the following question arises: given a set of target metabolites T and a set of possible external source metabolites , which are the minimal subsets of that are able to produce all the metabolites in T. Such subsets are called the minimal precursor sets of T. The problem is then whether we can enumerate all of them efficiently.<\/jats:p><jats:p>Results: We propose a new characterization of precursor sets as the inputs of reaction sets called factories and an efficient algorithm to decide if a set of sources is precursor set of T. We show proofs of hardness for the problems of finding a precursor set of minimum size and of enumerating all minimal precursor sets T. We propose two new algorithms which, despite the hardness of the enumeration problem, allow to enumerate all minimal precursor sets in networks with up to 1000 reactions.<\/jats:p><jats:p>Availability: Source code and datasets used in our benchmarks are freely available for download at http:\/\/sites.google.com\/site\/pitufosoftware\/download.<\/jats:p><jats:p>Contact: \u00a0vicente77@gmail.com, pvmilreu@gmail.com or marie-france.sagot@inria.fr<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts423","type":"journal-article","created":{"date-parts":[[2012,7,11]],"date-time":"2012-07-11T02:46:38Z","timestamp":1341974798000},"page":"2474-2483","source":"Crossref","is-referenced-by-count":20,"title":["Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks"],"prefix":"10.1093","volume":"28","author":[{"given":"Vicente","family":"Acu\u00f1a","sequence":"first","affiliation":[{"name":"1 Universit\u00e9 de Lyon, F-69000 Lyon, Universit\u00e9 Lyon 1, CNRS, UMR5558, Laboratoire de Biom\u00e9trie et Biologie Evolutive, F-69622 Villeurbanne, France, 2Mathomics, Center for Genome Regulation (Fondap 15090007) and Center for Mathematical Modeling (UMI 2807 CNRS), University of Chile, Santiago, Chile, 3INRIA Rh\u00f4ne-Alpes, 38330 Montbonnot Saint-Martin, France, 4Laboratoire d'Ing\u00e9nierie des Syst\u00e8mes Biologiques et des Proc\u00e9d\u00e9s (LISBP), UMR CNRS 5504, INRA 792, Toulouse, 31000, France, 5Dip. di Informatica e Sistemistica, University of Rome La Sapienza, 00184, Rome, Italy, and 6Department of Economics and Business Administration, VU University, 1087 HV Amsterdam and Centrum voor Wiskunde en Informatica (CWI), 1098 XG Amsterdam, The Netherlands"},{"name":"1 Universit\u00e9 de Lyon, F-69000 Lyon, Universit\u00e9 Lyon 1, CNRS, UMR5558, Laboratoire de Biom\u00e9trie et Biologie Evolutive, F-69622 Villeurbanne, France, 2Mathomics, Center for Genome Regulation (Fondap 15090007) and Center for Mathematical Modeling (UMI 2807 CNRS), University of Chile, Santiago, Chile, 3INRIA Rh\u00f4ne-Alpes, 38330 Montbonnot Saint-Martin, France, 4Laboratoire d'Ing\u00e9nierie des Syst\u00e8mes Biologiques et des Proc\u00e9d\u00e9s (LISBP), UMR CNRS 5504, INRA 792, Toulouse, 31000, France, 5Dip. di Informatica e Sistemistica, University of Rome La Sapienza, 00184, Rome, Italy, and 6Department of Economics and Business Administration, VU University, 1087 HV Amsterdam and Centrum voor Wiskunde en Informatica (CWI), 1098 XG Amsterdam, The Netherlands"},{"name":"1 Universit\u00e9 de Lyon, F-69000 Lyon, Universit\u00e9 Lyon 1, CNRS, UMR5558, Laboratoire de Biom\u00e9trie et Biologie Evolutive, F-69622 Villeurbanne, France, 2Mathomics, Center for Genome Regulation (Fondap 15090007) and Center for Mathematical Modeling (UMI 2807 CNRS), University of Chile, Santiago, Chile, 3INRIA Rh\u00f4ne-Alpes, 38330 Montbonnot Saint-Martin, France, 4Laboratoire d'Ing\u00e9nierie des Syst\u00e8mes Biologiques et des Proc\u00e9d\u00e9s (LISBP), UMR CNRS 5504, INRA 792, Toulouse, 31000, France, 5Dip. di Informatica e Sistemistica, University of Rome La Sapienza, 00184, Rome, Italy, and 6Department of Economics and Business Administration, VU University, 1087 HV Amsterdam and Centrum voor Wiskunde en Informatica (CWI), 1098 XG Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paulo Vieira","family":"Milreu","sequence":"additional","affiliation":[{"name":"1 Universit\u00e9 de Lyon, F-69000 Lyon, Universit\u00e9 Lyon 1, CNRS, UMR5558, Laboratoire de Biom\u00e9trie et Biologie Evolutive, F-69622 Villeurbanne, France, 2Mathomics, Center for Genome Regulation (Fondap 15090007) and Center for Mathematical Modeling (UMI 2807 CNRS), University of Chile, Santiago, Chile, 3INRIA Rh\u00f4ne-Alpes, 38330 Montbonnot Saint-Martin, France, 4Laboratoire d'Ing\u00e9nierie des Syst\u00e8mes Biologiques et des Proc\u00e9d\u00e9s (LISBP), UMR CNRS 5504, INRA 792, Toulouse, 31000, France, 5Dip. di Informatica e Sistemistica, University of Rome La Sapienza, 00184, Rome, Italy, and 6Department of Economics and Business Administration, VU University, 1087 HV Amsterdam and Centrum voor Wiskunde en Informatica (CWI), 1098 XG Amsterdam, The Netherlands"},{"name":"1 Universit\u00e9 de Lyon, F-69000 Lyon, Universit\u00e9 Lyon 1, CNRS, UMR5558, Laboratoire de Biom\u00e9trie et Biologie Evolutive, F-69622 Villeurbanne, France, 2Mathomics, Center for Genome Regulation (Fondap 15090007) and Center for Mathematical Modeling (UMI 2807 CNRS), University of Chile, Santiago, Chile, 3INRIA Rh\u00f4ne-Alpes, 38330 Montbonnot Saint-Martin, France, 4Laboratoire d'Ing\u00e9nierie des Syst\u00e8mes Biologiques et des Proc\u00e9d\u00e9s (LISBP), UMR CNRS 5504, INRA 792, Toulouse, 31000, France, 5Dip. di Informatica e Sistemistica, University of Rome La Sapienza, 00184, Rome, Italy, and 6Department of Economics and Business Administration, VU University, 1087 HV Amsterdam and Centrum voor Wiskunde en Informatica (CWI), 1098 XG Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ludovic","family":"Cottret","sequence":"additional","affiliation":[{"name":"1 Universit\u00e9 de Lyon, F-69000 Lyon, Universit\u00e9 Lyon 1, CNRS, UMR5558, Laboratoire de Biom\u00e9trie et Biologie Evolutive, F-69622 Villeurbanne, France, 2Mathomics, Center for Genome Regulation (Fondap 15090007) and Center for Mathematical Modeling (UMI 2807 CNRS), University of Chile, Santiago, Chile, 3INRIA Rh\u00f4ne-Alpes, 38330 Montbonnot Saint-Martin, France, 4Laboratoire d'Ing\u00e9nierie des Syst\u00e8mes Biologiques et des Proc\u00e9d\u00e9s (LISBP), UMR CNRS 5504, INRA 792, Toulouse, 31000, France, 5Dip. di Informatica e Sistemistica, University of Rome La Sapienza, 00184, Rome, Italy, and 6Department of Economics and Business Administration, VU University, 1087 HV Amsterdam and Centrum voor Wiskunde en Informatica (CWI), 1098 XG Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[{"name":"1 Universit\u00e9 de Lyon, F-69000 Lyon, Universit\u00e9 Lyon 1, CNRS, UMR5558, Laboratoire de Biom\u00e9trie et Biologie Evolutive, F-69622 Villeurbanne, France, 2Mathomics, Center for Genome Regulation (Fondap 15090007) and Center for Mathematical Modeling (UMI 2807 CNRS), University of Chile, Santiago, Chile, 3INRIA Rh\u00f4ne-Alpes, 38330 Montbonnot Saint-Martin, France, 4Laboratoire d'Ing\u00e9nierie des Syst\u00e8mes Biologiques et des Proc\u00e9d\u00e9s (LISBP), UMR CNRS 5504, INRA 792, Toulouse, 31000, France, 5Dip. di Informatica e Sistemistica, University of Rome La Sapienza, 00184, Rome, Italy, and 6Department of Economics and Business Administration, VU University, 1087 HV Amsterdam and Centrum voor Wiskunde en Informatica (CWI), 1098 XG Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[{"name":"1 Universit\u00e9 de Lyon, F-69000 Lyon, Universit\u00e9 Lyon 1, CNRS, UMR5558, Laboratoire de Biom\u00e9trie et Biologie Evolutive, F-69622 Villeurbanne, France, 2Mathomics, Center for Genome Regulation (Fondap 15090007) and Center for Mathematical Modeling (UMI 2807 CNRS), University of Chile, Santiago, Chile, 3INRIA Rh\u00f4ne-Alpes, 38330 Montbonnot Saint-Martin, France, 4Laboratoire d'Ing\u00e9nierie des Syst\u00e8mes Biologiques et des Proc\u00e9d\u00e9s (LISBP), UMR CNRS 5504, INRA 792, Toulouse, 31000, France, 5Dip. di Informatica e Sistemistica, University of Rome La Sapienza, 00184, Rome, Italy, and 6Department of Economics and Business Administration, VU University, 1087 HV Amsterdam and Centrum voor Wiskunde en Informatica (CWI), 1098 XG Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marie-France","family":"Sagot","sequence":"additional","affiliation":[{"name":"1 Universit\u00e9 de Lyon, F-69000 Lyon, Universit\u00e9 Lyon 1, CNRS, UMR5558, Laboratoire de Biom\u00e9trie et Biologie Evolutive, F-69622 Villeurbanne, France, 2Mathomics, Center for Genome Regulation (Fondap 15090007) and Center for Mathematical Modeling (UMI 2807 CNRS), University of Chile, Santiago, Chile, 3INRIA Rh\u00f4ne-Alpes, 38330 Montbonnot Saint-Martin, France, 4Laboratoire d'Ing\u00e9nierie des Syst\u00e8mes Biologiques et des Proc\u00e9d\u00e9s (LISBP), UMR CNRS 5504, INRA 792, Toulouse, 31000, France, 5Dip. di Informatica e Sistemistica, University of Rome La Sapienza, 00184, Rome, Italy, and 6Department of Economics and Business Administration, VU University, 1087 HV Amsterdam and Centrum voor Wiskunde en Informatica (CWI), 1098 XG Amsterdam, The Netherlands"},{"name":"1 Universit\u00e9 de Lyon, F-69000 Lyon, Universit\u00e9 Lyon 1, CNRS, UMR5558, Laboratoire de Biom\u00e9trie et Biologie Evolutive, F-69622 Villeurbanne, France, 2Mathomics, Center for Genome Regulation (Fondap 15090007) and Center for Mathematical Modeling (UMI 2807 CNRS), University of Chile, Santiago, Chile, 3INRIA Rh\u00f4ne-Alpes, 38330 Montbonnot Saint-Martin, France, 4Laboratoire d'Ing\u00e9nierie des Syst\u00e8mes Biologiques et des Proc\u00e9d\u00e9s (LISBP), UMR CNRS 5504, INRA 792, Toulouse, 31000, France, 5Dip. di Informatica e Sistemistica, University of Rome La Sapienza, 00184, Rome, Italy, and 6Department of Economics and Business Administration, VU University, 1087 HV Amsterdam and Centrum voor Wiskunde en Informatica (CWI), 1098 XG Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2012,7,10]]},"reference":[{"key":"2023012513061849700_bts423-B1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"Ausiello","year":"1999"},{"key":"2023012513061849700_bts423-B2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/978-3-540-87361-7_20","article-title":"Enumerating precursor sets of target metabolites in a metabolic network","volume-title":"Proceedings of the 8th International Workshop on Algorithms in Bioinformatics (WABI)","author":"Cottret","year":"2008"},{"key":"2023012513061849700_bts423-B3","doi-asserted-by":"crossref","first-page":"e1000904","DOI":"10.1371\/journal.pcbi.1000904","article-title":"A Graph-based analysis of the metabolic exchanges between two co-resident intracellular symbionts, Baumannia cicadellinicola and Sulcia muelleri, with their insect host, Homalodisca coagulata","volume":"6","author":"Cottret","year":"2010","journal-title":"PLoS Comput. Biol."},{"key":"2023012513061849700_bts423-B4","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1093\/nar\/gkq312","article-title":"Metexplore: a web server to link metabolomic experiments and genome-scale metabolic networks","volume":"38","author":"Cottret","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023012513061849700_bts423-B5","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1038\/nrmicro1949","article-title":"Reconstruction of biochemical networks in microorganisms","volume":"7","author":"Feist","year":"2009","journal-title":"Nat. Rev. Microbiol."},{"key":"2023012513061849700_bts423-B6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of books in the mathematical sciences","author":"Garey","year":"1979"},{"key":"2023012513061849700_bts423-B7","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/S0166-218X(99)00099-2","article-title":"On generating the irredundant conjunctive and disjunctive normal forms of monotone boolean functions","volume":"96\u201397","author":"Gurvich","year":"1999","journal-title":"Discrete Appl. Math."},{"key":"2023012513061849700_bts423-B8","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","article-title":"On generating all maximal independent sets","volume":"27","author":"Johnson","year":"1988","journal-title":"Inform. Process. Lett."},{"key":"2023012513061849700_bts423-B9","doi-asserted-by":"crossref","first-page":"19392","DOI":"10.1073\/pnas.0708855104","article-title":"Parallel genomic evolution and metabolic interdependence in an ancient symbiosis","volume":"104","author":"McCutcheon","year":"2007","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012513061849700_bts423-B10","doi-asserted-by":"crossref","DOI":"10.1145\/258533.258641","article-title":"A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP","volume-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing","author":"Raz","year":"1997"},{"key":"2023012513061849700_bts423-B11","first-page":"470","article-title":"Nutrition-related analysis of pathway\/genome databases","volume-title":"Pacific Symposium on Biocomputing'01","author":"Romero","year":"2001"},{"key":"2023012513061849700_bts423-B12","doi-asserted-by":"crossref","first-page":"1750","DOI":"10.1038\/nprot.2009.203","article-title":"A protocol for generating a high-quality genome-scale metabolic reconstruction","volume":"5","author":"Thiele","year":"2010","journal-title":"Nat. Protoc."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/19\/2474\/48882063\/bioinformatics_28_19_2474.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/19\/2474\/48882063\/bioinformatics_28_19_2474.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T18:01:23Z","timestamp":1714154483000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/19\/2474\/287819"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,10]]},"references-count":12,"journal-issue":{"issue":"19","published-print":{"date-parts":[[2012,10,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts423","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,10,1]]},"published":{"date-parts":[[2012,7,10]]}}}