A mixed-integer linear programming approach to the reduction of genome-scale metabolic networks

BMC Bioinformatics

Methodology Article

Annika Röhl¹  Alexander Bockmayr¹ 

[1] Department of Mathematics and Computer Science, Freie Universität Berlin, Arnimallee 6, Berlin, Germany;

关键词: Constraint-based modeling;    Model reduction;    Stoichiometric models;    Mixed-integer linear programming;    Metabolic networks;   

DOI  :  10.1186/s12859-016-1412-z

 received in 2016-08-04, accepted in 2016-12-07,  发布年份 2017

来源: Springer

【 摘 要 】

BackgroundConstraint-based analysis has become a widely used method to study metabolic networks. While some of the associated algorithms can be applied to genome-scale network reconstructions with several thousands of reactions, others are limited to small or medium-sized models. In 2015, Erdrich et al. introduced a method called NetworkReducer, which reduces large metabolic networks to smaller subnetworks, while preserving a set of biological requirements that can be specified by the user. Already in 2001, Burgard et al. developed a mixed-integer linear programming (MILP) approach for computing minimal reaction sets under a given growth requirement.ResultsHere we present an MILP approach for computing minimum subnetworks with the given properties. The minimality (with respect to the number of active reactions) is not guaranteed by NetworkReducer, while the method by Burgard et al. does not allow specifying the different biological requirements. Our procedure is about 5-10 times faster than NetworkReducer and can enumerate all minimum subnetworks in case there exist several ones. This allows identifying common reactions that are present in all subnetworks, and reactions appearing in alternative pathways.ConclusionsApplying complex analysis methods to genome-scale metabolic networks is often not possible in practice. Thus it may become necessary to reduce the size of the network while keeping important functionalities. We propose a MILP solution to this problem. Compared to previous work, our approach is more efficient and allows computing not only one, but even all minimum subnetworks satisfying the required properties.

【 授权许可】

CC BY   
© The Author(s) 2017

【 图 表 】

12864_2017_3990_Article_IEq6.gif

12864_2015_2129_Article_IEq5.gif

12864_2017_3610_Article_IEq1.gif

12864_2016_3425_Article_IEq1.gif

12864_2017_3487_Article_IEq20.gif

12864_2017_3487_Article_IEq18.gif

12864_2017_3487_Article_IEq17.gif

12898_2017_155_Article_IEq33.gif

12864_2017_3487_Article_IEq16.gif

12888_2016_877_Article_IEq10.gif

12864_2017_3733_Article_IEq17.gif

12870_2017_1059_Article_IEq7.gif

12864_2015_2192_Article_IEq13.gif

12864_2017_3547_Article_IEq1.gif

12864_2015_2192_Article_IEq11.gif

12864_2016_3440_Article_IEq55.gif

12864_2016_3440_Article_IEq53.gif

12902_2017_191_Article_IEq1.gif

12864_2017_3670_Article_IEq8.gif

12864_2015_2214_Article_IEq2.gif

12864_2017_4186_Article_IEq17.gif

12864_2017_4186_Article_IEq15.gif

12864_2017_3938_Article_IEq14.gif

12864_2017_3790_Article_IEq1.gif

12864_2015_2055_Article_IEq89.gif

12864_2015_2300_Article_IEq4.gif

12864_2017_3670_Article_IEq3.gif

12880_2016_125_Article_IEq21.gif

12864_2016_3317_Article_IEq1.gif

12864_2017_3670_Article_IEq1.gif