Presentation	2009-10-16 Algorithm for Finding Minimum Reaction Cut of Metabolic Network Takeyuki TAMURA, Kazuhiro TAKEMOTO, Tatsuya AKUTSU,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	In this article, we study two problems ReactionCut and MD-ReactionCut for calculating minimum reaction cuts of a metabolic network under a Boolean model. These problems are based on flux balance model and minimal damage model respectively. We show that ReactionCut and MD-ReactionCut are NP-hard even if the maximum outdegree of reaction nodes (K_) is one. We also present O(1.822^n), O(1.959^n) and o(2^n) time algorithms for MD-ReactionCut with K_=2, 3, k respectively where n is the number of reaction nodes and k is a constant. The same algorithms also work for ReactionCut if there is no cycle.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Metabolic network / Reaction cut / Boolean model / Robustness
Paper #	COMP2009-36
Date of Issue

Conference Information
Committee	COMP
Conference Date	2009/10/9(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Algorithm for Finding Minimum Reaction Cut of Metabolic Network
Sub Title (in English)
Keyword(1)	Metabolic network
Keyword(2)	Reaction cut
Keyword(3)	Boolean model
Keyword(4)	Robustness
1st Author's Name	Takeyuki TAMURA
1st Author's Affiliation	Bioinformatics Center, Institute for Chemical Research, Kyoto University()
2nd Author's Name	Kazuhiro TAKEMOTO
2nd Author's Affiliation	Graduate School of Frontier Sciences, University of Tokyo
3rd Author's Name	Tatsuya AKUTSU
3rd Author's Affiliation	Bioinformatics Center, Institute for Chemical Research, Kyoto University
Date	2009-10-16
Paper #	COMP2009-36
Volume (vol)	vol.109
Number (no)	235
Page	pp.pp.-
#Pages	8
Date of Issue