Integer programming-based method for designing synthetic metabolic networks by Minimum Reaction Insertion in a Boolean model.

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. Althoug...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Wei Lu, Takeyuki Tamura, Jiangning Song, Tatsuya Akutsu
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2014
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/4d242125653f4e2ab3ef0c1e5f75ddd6
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:4d242125653f4e2ab3ef0c1e5f75ddd6
record_format	dspace
spelling	oai:doaj.org-article:4d242125653f4e2ab3ef0c1e5f75ddd62021-11-18T08:27:05ZInteger programming-based method for designing synthetic metabolic networks by Minimum Reaction Insertion in a Boolean model.1932-620310.1371/journal.pone.0092637https://doaj.org/article/4d242125653f4e2ab3ef0c1e5f75ddd62014-01-01T00:00:00Zhttps://www.ncbi.nlm.nih.gov/pmc/articles/pmid/24651476/?tool=EBIhttps://doaj.org/toc/1932-6203In 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/~rogi/minRect/minRect.html."Wei LuTakeyuki TamuraJiangning SongTatsuya AkutsuPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 9, Iss 3, p e92637 (2014)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Wei Lu Takeyuki Tamura Jiangning Song Tatsuya Akutsu Integer programming-based method for designing synthetic metabolic networks by Minimum Reaction Insertion in a Boolean model.
description	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/~rogi/minRect/minRect.html."
format	article
author	Wei Lu Takeyuki Tamura Jiangning Song Tatsuya Akutsu
author_facet	Wei Lu Takeyuki Tamura Jiangning Song Tatsuya Akutsu
author_sort	Wei Lu
title	Integer programming-based method for designing synthetic metabolic networks by Minimum Reaction Insertion in a Boolean model.
title_short	Integer programming-based method for designing synthetic metabolic networks by Minimum Reaction Insertion in a Boolean model.
title_full	Integer programming-based method for designing synthetic metabolic networks by Minimum Reaction Insertion in a Boolean model.
title_fullStr	Integer programming-based method for designing synthetic metabolic networks by Minimum Reaction Insertion in a Boolean model.
title_full_unstemmed	Integer programming-based method for designing synthetic metabolic networks by Minimum Reaction Insertion in a Boolean model.
title_sort	integer programming-based method for designing synthetic metabolic networks by minimum reaction insertion in a boolean model.
publisher	Public Library of Science (PLoS)
publishDate	2014
url	https://doaj.org/article/4d242125653f4e2ab3ef0c1e5f75ddd6
work_keys_str_mv	AT weilu integerprogrammingbasedmethodfordesigningsyntheticmetabolicnetworksbyminimumreactioninsertioninabooleanmodel AT takeyukitamura integerprogrammingbasedmethodfordesigningsyntheticmetabolicnetworksbyminimumreactioninsertioninabooleanmodel AT jiangningsong integerprogrammingbasedmethodfordesigningsyntheticmetabolicnetworksbyminimumreactioninsertioninabooleanmodel AT tatsuyaakutsu integerprogrammingbasedmethodfordesigningsyntheticmetabolicnetworksbyminimumreactioninsertioninabooleanmodel
_version_	1718421799771832320

Integer programming-based method for designing synthetic metabolic networks by Minimum Reaction Insertion in a Boolean model.

Ejemplares similares