Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks
Authors:
- Vicente AcuñaVAVicente Acuña
- Paulo Vieira MilreuPMPaulo Vieira Milreu
- Ludovic CottretLCLudovic Cottret
- Alberto Marchetti-SpaccamelaAMAlberto Marchetti-Spaccamela
- Leen StougieLSLeen Stougie
- Marie-France SagotMSMarie-France Sagot
- 10 July 2012
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 28 (19) , 2474-2483
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- Graph-Based Analysis of the Metabolic Exchanges between Two Co-Resident Intracellular Symbionts, Baumannia cicadellinicola and Sulcia muelleri, with Their Insect Host, Homalodisca coagulataPLOS Computational Biology, 2010
- MetExplore: a web server to link metabolomic experiments and genome-scale metabolic networksNucleic Acids Research, 2010
- A protocol for generating a high-quality genome-scale metabolic reconstructionNature Protocols, 2010
- Reconstruction of biochemical networks in microorganismsNature Reviews Microbiology, 2008
- Enumerating Precursor Sets of Target Metabolites in a Metabolic Network2008
- Parallel genomic evolution and metabolic interdependence in an ancient symbiosisProceedings of the National Academy of Sciences, 2007
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functionsDiscrete Applied Mathematics, 1999
- Complexity and Approximation1999
- A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP1997
- On generating all maximal independent setsInformation Processing Letters, 1988