Enumerating Chemical Organisations in Consistent Metabolic Networks: Complexity and Algorithms

Paulo Milreu; Vicente Acuña; Etienne Birmelé; Pierluigi Crescenzi; Alberto Marchetti-Spaccamela; Marie-France Sagot; Leen Stougie; Vincent Lacroix

Enumerating Chemical Organisations in Consistent Metabolic Networks: Complexity and Algorithms

Paulo Milreu ^{1, *} Vicente Acuña ¹ Etienne Birmelé ² Pierluigi Crescenzi ³ Alberto Marchetti-Spaccamela ⁴ Marie-France Sagot ¹ Leen Stougie ^{5, 6} Vincent Lacroix ¹

* Corresponding author

1 BAMBOO - An algorithmic view on genomes, cells, and environments

Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558

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.

Document type :

Conference papers

Domain :

Mathematics [math] / Combinatorics [math.CO]

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

Complete list of metadatas

Cited literature [13 references] Display Hide Download

https://hal.inria.fr/hal-00751339
Contributor : Marie-France Sagot <>
Submitted on : Tuesday, November 13, 2012 - 11:22:17 AM
Last modification on : Friday, September 27, 2019 - 10:10:18 AM
Long-term archiving on : Thursday, February 14, 2013 - 3:41:04 AM

Enumerating_Chemical_Organisat...

Files produced by the author(s)

Enumerating Chemical Organisations in Consistent Metabolic Networks: Complexity and Algorithms

File

Identifiers

Collections

Citation

Export

Metrics

776

234

Contact

Enumerating Chemical Organisations in Consistent Metabolic Networks: Complexity and Algorithms

File

Identifiers

Collections

Citation

Export

Share

Metrics

776

234

Contact