Constraint-based approaches recently brought new insight into our understanding of metabolism. By making very simple assumptions such as that the system is at steady-state and some reactions are irreversible, and without requiring kinetic parameters, general properties of the system can be derived. A central concept in this methodology is the notion of an elementary mode (EM for short) which represents a minimal functional subsystem. The computation of EMs still forms a limiting step in metabolic studies and several algorithms have been proposed to address this problem leading to increasingly faster methods. However, although a theoretical upper bound on the number of elementary modes that a network may possess has been established, surprisingly, the complexity of this problem has never been systematically studied. In this paper, we give a systematic overview of the complexity of optimisation problems related to modes. We first establish results regarding network consistency. Most consistency problems are easy, i.e., they can be solved in polynomial time, We then establish the complexity of finding and counting elementary modes. We show in particular that finding one elementary mode is easy but that this task becomes hard when a specific EM (i.e. an EM containing some specified reactions) is sought. We then show that counting the number of elementary modes is #P-complete. We emphasize that the easy problems can be solved using Currently existing software packages. We then analyse the complexity of a closely related task which is the computation of so-called minimum reaction cut sets and we show that this problem is hard. We then present two positive results which both allow to avoid computing EMs as a prior to the computation of reaction cuts. The first one is a polynomial approximation algorithm for finding a minimum reaction cut set. The second one is a test for verifying whether a set of reactions constitutes a reaction Cut; this test can be readily included in existing algorithms to improve their performance. Finally, we discuss the complexity of other cut-related problems. (C) 2008 Elsevier Ireland Ltd. All rights reserved.

Modes and cuts in metabolic networks: Complexity and algorithms / Vicente, Acuna; Chierichetti, Flavio; Vincent, Lacroix; MARCHETTI SPACCAMELA, Alberto; Marie France, Sagot; Leen, Stougie. - In: BIOSYSTEMS. - ISSN 0303-2647. - STAMPA. - 95:1(2009), pp. 51-60. [10.1016/j.biosystems.2008.06.015]

Modes and cuts in metabolic networks: Complexity and algorithms

CHIERICHETTI, FLAVIO;MARCHETTI SPACCAMELA, Alberto;
2009

Abstract

Constraint-based approaches recently brought new insight into our understanding of metabolism. By making very simple assumptions such as that the system is at steady-state and some reactions are irreversible, and without requiring kinetic parameters, general properties of the system can be derived. A central concept in this methodology is the notion of an elementary mode (EM for short) which represents a minimal functional subsystem. The computation of EMs still forms a limiting step in metabolic studies and several algorithms have been proposed to address this problem leading to increasingly faster methods. However, although a theoretical upper bound on the number of elementary modes that a network may possess has been established, surprisingly, the complexity of this problem has never been systematically studied. In this paper, we give a systematic overview of the complexity of optimisation problems related to modes. We first establish results regarding network consistency. Most consistency problems are easy, i.e., they can be solved in polynomial time, We then establish the complexity of finding and counting elementary modes. We show in particular that finding one elementary mode is easy but that this task becomes hard when a specific EM (i.e. an EM containing some specified reactions) is sought. We then show that counting the number of elementary modes is #P-complete. We emphasize that the easy problems can be solved using Currently existing software packages. We then analyse the complexity of a closely related task which is the computation of so-called minimum reaction cut sets and we show that this problem is hard. We then present two positive results which both allow to avoid computing EMs as a prior to the computation of reaction cuts. The first one is a polynomial approximation algorithm for finding a minimum reaction cut set. The second one is a test for verifying whether a set of reactions constitutes a reaction Cut; this test can be readily included in existing algorithms to improve their performance. Finally, we discuss the complexity of other cut-related problems. (C) 2008 Elsevier Ireland Ltd. All rights reserved.
2009
algorithms; computational complexity; enumeration; linear programming; metabolic networks; stoichiometry
01 Pubblicazione su rivista::01a Articolo in rivista
Modes and cuts in metabolic networks: Complexity and algorithms / Vicente, Acuna; Chierichetti, Flavio; Vincent, Lacroix; MARCHETTI SPACCAMELA, Alberto; Marie France, Sagot; Leen, Stougie. - In: BIOSYSTEMS. - ISSN 0303-2647. - STAMPA. - 95:1(2009), pp. 51-60. [10.1016/j.biosystems.2008.06.015]
File allegati a questo prodotto
File Dimensione Formato  
VE_2009_11573-362332.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 327.84 kB
Formato Adobe PDF
327.84 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/362332
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? 22
  • Scopus 76
  • ???jsp.display-item.citation.isi??? 67
social impact