Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks.

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. 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. AVAILABILITY: Source code and datasets used in our benchmarks are freely available for download at http://sites.google.com/site/pitufosoftware/download. CONTACT: vicente77@gmail.com, pvmilreu@gmail.com or marie-france.sagot@inria.fr.
Type de document :
Article dans une revue
Bioinformatics, Oxford University Press (OUP), 2012, 28 (19), pp.2474-2483. 〈10.1093/bioinformatics/bts423〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00751715
Contributeur : Marie-France Sagot <>
Soumis le : mercredi 14 novembre 2012 - 10:00:20
Dernière modification le : jeudi 28 juin 2018 - 14:38:25

Lien texte intégral

Identifiants

Collections

Citation

Vicente Acuña, Paulo Vieira Milreu, Ludovic Cottret, Alberto Marchetti-Spaccamela, Leen Stougie, et al.. Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks.. Bioinformatics, Oxford University Press (OUP), 2012, 28 (19), pp.2474-2483. 〈10.1093/bioinformatics/bts423〉. 〈hal-00751715〉

Partager

Métriques

Consultations de la notice

385