Enumerating Chemical Organisations in Consistent Metabolic Networks: Complexity and Algorithms

Paulo Milreu 1, * Vicente Acuña 1 Etienne Birmelé 2 Pierluigi Crescenzi 3 Alberto Marchetti-Spaccamela 4 Marie-France Sagot 1 Leen Stougie 5, 6 Vincent Lacroix 1
* Auteur correspondant
1 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive
2 SG - Laboratoire Statistique et Génome
3 DSI - Dipartimento di Sistemi e Informatica
4 DIS - Dipartimento di Informatica e Sistemistica "Antonio Ruberti"
5 VU - Computational Intelligence Group Department of Conputer Science
6 CWI - Centrum voor Wiskunde en Informatica
Abstract : The structural analysis of metabolic networks aims both at understanding the function and the evolution of metabolism. While it is commonly admitted that metabolism is modular, the identi cation of metabolic modules remains an open topic. Several de nitions of what is a module have been proposed. We focus here on the notion of chemical organisations, i.e. sets of molecules which are closed and self-maintaining. We show that nding a reactive organisation is NP-hard even if the network is mass- and ux-consistent and that the hardness comes from blocking cycles. We then propose new algorithms for enumerating chemical organisations that are theoretically more e cient than existing approaches.
Type de document :
Communication dans un congrès
Moulton, Vincent and Singh, Mona. Workshop on Algorithms in Bioinformatics (WABI), Sep 2010, Liverpool, United Kingdom. Springer Berlin Heidelberg, 6293, pp.226-237, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-15294-8_19〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00751339
Contributeur : Marie-France Sagot <>
Soumis le : mardi 13 novembre 2012 - 11:22:17
Dernière modification le : jeudi 28 juin 2018 - 14:38:28
Document(s) archivé(s) le : jeudi 14 février 2013 - 03:41:04

Fichier

Enumerating_Chemical_Organisat...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | INSMI | BAMBOO | BIOENVIS | INRA | UNIV-LYON1

Citation

Paulo Milreu, Vicente Acuña, Etienne Birmelé, Pierluigi Crescenzi, Alberto Marchetti-Spaccamela, et al.. Enumerating Chemical Organisations in Consistent Metabolic Networks: Complexity and Algorithms. Moulton, Vincent and Singh, Mona. Workshop on Algorithms in Bioinformatics (WABI), Sep 2010, Liverpool, United Kingdom. Springer Berlin Heidelberg, 6293, pp.226-237, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-15294-8_19〉. 〈hal-00751339〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

651

Téléchargements de fichiers

112

Contact


archive-ouverte@inria.fr