A note on the complexity of finding and enumerating elementary modes

被引：36

作者：

Acuna, Vicente ^{[1
,2
,3
]}

Marchetti-Spaccamela, Alberto ^{[4
]}

Sagot, Marie-France ^{[1
,2
,3
]}

Stougie, Leen ^{[5
,6
]}

机构：

[1] Univ Lyon, F-69000 Lyon, France

[2] Univ Lyon 1, CNRS, UMR5558, Lab Biometrie & Biol Evolut, F-69622 Villeurbanne, France

[3] INRIA Rhone Alpes, F-38330 Montbonnot St Martin, France

[4] Univ Roma La Sapienza, I-00184 Rome, Italy

[5] Vrije Univ Amsterdam, NL-1081 HV Amsterdam, Netherlands

[6] Ctr Wiskunde & Informat, NL-1098 SJ Amsterdam, Netherlands

来源：

BIOSYSTEMS | 2010年 / 99卷 / 03期

基金：

英国生物技术与生命科学研究理事会;

关键词：

Metabolic networks; Computational complexity; Elementary modes; Enumeration; GENOME-SCALE MODEL; METABOLIC NETWORKS; STRATEGIES; ALGORITHM; SYSTEMS;

D O I：

10.1016/j.biosystems.2009.11.004

中图分类号：

Q [生物科学];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

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. (C) 2009 Elsevier Ireland Ltd. All rights reserved.

引用

页码：210 / 214

页数：5

共 25 条

[1] Modes and cuts in metabolic networks: Complexity and algorithms [J].