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

V. Acuna, P. Vieira Milreu, L. Cottret, A. Marchetti-Spaccamela, L. Stougie, M.-F. Sagot

Research output: Contribution to JournalArticleAcademicpeer-review

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.© The Author 2012. Published by Oxford University Press.
Original languageEnglish
Pages (from-to)2474-2483
JournalBioinformatics
Volume28
Issue number19
DOIs
Publication statusPublished - 2012

Fingerprint

Metabolic Network
Hardness
Metabolites
Metabolic Networks and Pathways
Precursor
Genome
Genes
Industrial plants
Subset
Enumeration
Efficient Algorithms
Target

Cite this

Acuna, V., Vieira Milreu, P., Cottret, L., Marchetti-Spaccamela, A., Stougie, L., & Sagot, M-F. (2012). Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks. Bioinformatics, 28(19), 2474-2483. https://doi.org/10.1093/bioinformatics/bts423
Acuna, V. ; Vieira Milreu, P. ; Cottret, L. ; Marchetti-Spaccamela, A. ; Stougie, L. ; Sagot, M.-F. / Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks. In: Bioinformatics. 2012 ; Vol. 28, No. 19. pp. 2474-2483.
@article{35ec651c8031473396bbd220cfa133c4,
title = "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.{\circledC} The Author 2012. Published by Oxford University Press.",
author = "V. Acuna and {Vieira Milreu}, P. and L. Cottret and A. Marchetti-Spaccamela and L. Stougie and M.-F. Sagot",
year = "2012",
doi = "10.1093/bioinformatics/bts423",
language = "English",
volume = "28",
pages = "2474--2483",
journal = "Bioinformatics",
issn = "1367-4803",
publisher = "Oxford University Press",
number = "19",

}

Acuna, V, Vieira Milreu, P, Cottret, L, Marchetti-Spaccamela, A, Stougie, L & Sagot, M-F 2012, 'Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks' Bioinformatics, vol. 28, no. 19, pp. 2474-2483. https://doi.org/10.1093/bioinformatics/bts423

Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks. / Acuna, V.; Vieira Milreu, P.; Cottret, L.; Marchetti-Spaccamela, A.; Stougie, L.; Sagot, M.-F.

In: Bioinformatics, Vol. 28, No. 19, 2012, p. 2474-2483.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

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

AU - Acuna, V.

AU - Vieira Milreu, P.

AU - Cottret, L.

AU - Marchetti-Spaccamela, A.

AU - Stougie, L.

AU - Sagot, M.-F.

PY - 2012

Y1 - 2012

N2 - 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.© The Author 2012. Published by Oxford University Press.

AB - 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.© The Author 2012. Published by Oxford University Press.

U2 - 10.1093/bioinformatics/bts423

DO - 10.1093/bioinformatics/bts423

M3 - Article

VL - 28

SP - 2474

EP - 2483

JO - Bioinformatics

JF - Bioinformatics

SN - 1367-4803

IS - 19

ER -