Parameterized Complezity of Inverse Scope Problems in Metabolic Networks

摘要：

Inverse Scope Problem aims to determine, by analyzing the structure of a metabolic network, the minimum cardinality set of seed compounds required for the synthesis of a specific compound or set of compounds. This paper examines the computational complexity of three variants of the inverse scope problem from parameterized complexity view. With as natural parameter the minimum number of metabolites necessary for synthesizing a set of target metabolites, we prove that inverse scope problem with two forbidden sets is W2-hard. In addition, we point out that the inverse scope problem with no forbidden set and the inverse scope problem with a forbidden set are also W2-hard.

作者: Hong Liu Haodi Feng Darning Zhu

作者单位: Algorithms Group, School of Computer Science and Technology Shandong University Jinan, Shandong Province, China

会议类型: 国际会议

会议名称: 2009 WASE International Conference on Information Engineering(2009年国际信息工程会议)(ICIE 2009)

会议地点: 太原

会议语种:英文

页码: 1053-1056

在线出版日期: 2009-07-10（万方平台首次上网日期，不代表论文的发表时间）