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

Vicente Acuña (1) , Alberto Marchetti-Spaccamela (2) , Marie-France Sagot (1) , Leen Stougie (3)

1 BAMBOO - An algorithmic view on genomes, cells, and environments
2 DIS - Dipartimento di Informatica e Sistemistica "Antonio Ruberti"
3 Department of mathematics and computing science [Eindhoven]

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.

Domaines: Algorithme et structure de données [cs.DS]; Bio-informatique [q-bio.QM]; Bio-Informatique, Biologie Systémique [q-bio.QM]

Vicente Acuña, Alberto Marchetti-Spaccamela, Marie-France Sagot, Leen Stougie. A note on the complexity of finding and enumerating elementary modes.. BioSystems, 2010, 99 (3), pp.210-4. ⟨10.1016/j.biosystems.2009.11.004⟩. ⟨hal-00845385⟩