A note on the complexity of finding and enumerating elementary modes.

0 avis

A note on the complexity of finding and enumerating elementary modes.

Archive ouverte

Acuña, Vicente | Marchetti-Spaccamela, Alberto | Sagot, Marie-France | Stougie, Leen

International audience. In the context of the study into elementary modes of metabolic networks, we prove two complexity results. Enumerating elementary modes containing a specific reaction is hard in an enumeration complexity sense. The decision problem if there exists an elementary mode containing two specific reactions is NP-complete. The complexity of enumerating all elementary modes remains open.

Langue: en

Indexation

Consulter en ligne

Consulter le document

Suggestions

Du même auteur

Telling metabolic stories to explore metabolomics data: a case study on the yeast response to cadmium exposure

Archive ouverte | Milreu, Paulo Vieira | CCSD

International audience. MOTIVATION: The increasing availability of metabolomics data enables to better understand the metabolic processes involved in the immediate response of an organism to environmental changes an...

Enumeration of minimal stoichiometric precursor sets in metabolic networks

Archive ouverte | Andrade, Ricardo | CCSD

International audience. Background : What an organism needs at least from its environment to produce a set of metabolites, e.g. target(s) of interest and/or biomass, has been called a minimal precursor set. Early ap...

Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets

Archive ouverte | Acuña, Vicente | CCSD

International audience. We present a constrained version of the problem of enumerating all maximal directed acyclic subgraphs (DAG) of a graph G. In this version, we enumerate maximal DAGs whose sources and targets ...

Chargement des enrichissements...