Integer Programming-Based Method for Designing Synthetic Metabolic Networks by Minimum Reaction Insertion in a Boolean Model

CORC > 天津工业生物技术研究所 > 结构生物信息学和整合系统生物学实验室宋江宁 > 期刊论文

	Integer Programming-Based Method for Designing Synthetic Metabolic Networks by Minimum Reaction Insertion in a Boolean Model
	Lu, Wei 1; Tamura, Takeyuki 1; Song, Jiangning 2,3; Akutsu, Tatsuya 1
刊名	PLOS ONE
	2014-03-20
卷号	9 期号:3
英文摘要	In this paper, we consider the Minimum Reaction Insertion (MRI) problem for finding the minimum number of additional reactions from a reference metabolic network to a host metabolic network so that a target compound becomes producible in the revised host metabolic network in a Boolean model. Although a similar problem for larger networks is solvable in a flux balance analysis (FBA)-based model, the solution of the FBA-based model tends to include more reactions than that of the Boolean model. However, solving MRI using the Boolean model is computationally more expensive than using the FBA-based model since the Boolean model needs more integer variables. Therefore, in this study, to solve MRI for larger networks in the Boolean model, we have developed an efficient Integer Programming formalization method in which the number of integer variables is reduced by the notion of feedback vertex set and minimal valid assignment. As a result of computer experiments conducted using the data of metabolic networks of E. coli and reference networks downloaded from the Kyoto Encyclopedia of Genes and Genomes (KEGG) database, we have found that the developed method can appropriately solve MRI in the Boolean model and is applicable to large scale-networks for which an exhaustive search does not work. We have also compared the developed method with the existing connectivity-based methods and FBA-based methods, and show the difference between the solutions of our method and the existing methods. A theoretical analysis of MRI is also conducted, and the NP-completeness of MRI is proved in the Boolean model. Our developed software is available at "http://sunflower.kuicr.kyoto-u.ac.jp/similar to rogi/minRect/minRect.html."
WOS标题词	Science & Technology
类目[WOS]	Multidisciplinary Sciences
研究领域[WOS]	Science & Technology - Other Topics
关键词[WOS]	ESCHERICHIA-COLI ; PATHWAYS ; ROBUSTNESS ; PREDICTION ; TARGETS
收录类别	SCI
语种	英语
WOS记录号	WOS:000333352800136
内容类型	期刊论文
源URL	[http://124.16.173.210/handle/834782/1399]
专题	天津工业生物技术研究所_结构生物信息学和整合系统生物学实验室宋江宁_期刊论文
作者单位	1.Kyoto Univ, Inst Chem Res, Bioinformat Ctr, Uji, Kyoto, Japan 2.Monash Univ, Dept Biochem & Mol Biol, Melbourne, Vic 3004, Australia 3.Chinese Acad Sci, Tianjin Inst Ind Biotechnol, Natl Engn Lab Ind Enzymes, Tianjin, Peoples R China
推荐引用方式 GB/T 7714	Lu, Wei,Tamura, Takeyuki,Song, Jiangning,et al. Integer Programming-Based Method for Designing Synthetic Metabolic Networks by Minimum Reaction Insertion in a Boolean Model[J]. PLOS ONE,2014,9(3).
APA	Lu, Wei,Tamura, Takeyuki,Song, Jiangning,&Akutsu, Tatsuya.(2014).Integer Programming-Based Method for Designing Synthetic Metabolic Networks by Minimum Reaction Insertion in a Boolean Model.PLOS ONE,9(3).
MLA	Lu, Wei,et al."Integer Programming-Based Method for Designing Synthetic Metabolic Networks by Minimum Reaction Insertion in a Boolean Model".PLOS ONE 9.3(2014).