Computing Minimum Reaction Modifications in a Boolean Metabolic Network

Takeyuki Tamura, Wei Lu, Jiangning Song, Tatsuya Akutsu

Research output: Contribution to journalArticleResearchpeer-review


In metabolic network modification, we newly add enzymes or/and knock-out genes to maximize the biomass production with minimum side-effect. Although this problem has been studied for various problem settings via mathematical models including flux balance analysis, elementary mode, and Boolean models, some important problem settings still remain to be studied. In this paper, we consider Boolean Reaction Modification (BRM) problem, where a host metabolic network and a reference metabolic network are given in the Boolean model, the host network initially produces some toxic compounds and cannot produce some necessary compounds, but the reference network can produce the necessary compounds, and we should minimize the total number of removed reactions from the host network and added reactions from the reference network so that the toxic compounds are not producible, but the necessary compounds are producible in the resulting host network. We developed integer linear programming (ILP)-based methods for BRM, and compared with OptStrain and SimOptStrain. The results show that our method performed better for reducing the total number of added and removed reactions, while OptStrain and SimOptStrain performed better for optimizing the production of the target compound. Our developed software is freely available at “”.

Original languageEnglish
Pages (from-to)1853-1862
Number of pages10
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Issue number6
Publication statusPublished - 24 Nov 2017


  • algorithm
  • Biochemistry
  • Bioinformatics
  • Biological system modeling
  • Biomass
  • Boolean model
  • Compounds
  • feedback vertex set
  • flux balance analysis
  • integer linear programming
  • Mathematical model
  • metabolic network
  • Production

Cite this