RegKnock: identifying gene knockout strategies for microbial strain optimization based on regulatory and metabolic integrated network

Background Gene knockout has been used to improve the conversion ratio of strains for some chemical products. Based on mixed integer bi-level linear programming (MIBLP) and cell network models, there have been several algorithms to predict the target for deletion to improve the productivity of chemicals. At present, the cell models on which these algorithms based have changed from metabolic network to metabolic-regulatory integrated network, for integrated network is more comprehensive in describing the behavior of cells. Metabolic-regulatory integrated network is better than metabolic network in flux prediction, but will introduce integer variables in the inner of MIBLP. How to solve the intractable MIBLP, however, is not explicated clearly as in mathematical literatures, especially for MIBLP with integer variables in the inner problem (named as MIBLP-2) where integer variables are introduced by the flux balance analysis (FBA) for integrated network. Dual theory was still be used to transform MIBLP-2 to a single level with ignoring integer variables in the inner problem. Intelligent computation is another choice for solving MIBLP, but it usually was used to solve the single level nonlinear programming (NLP) which was the transformation from MIBLP by using joint objective of upper/lower level, while the equivalence between this MIBLP and this NLP was not be proved in mathematics. Methods In this study, we develop a new target predicting algorithm for gene knockouts, named RegKnock. The cell model on which we base is metabolic-regulatory integrated network as well. When solving the MIBLP-2, RegKnock uses Parallel Genetic Algorithm (PGA), but not use joint objective. GA was used to generate control variables of the upper, indicating which genes should be deleted, while the fitness function is to maximize the objective product calculated from the inner FBA of the integrated network. FBA of the inner problem, a mixed integer programming, could be solved by existing optimization softwares. Parallel computation aims to accelerate finding the optimal solution and thus decreases the time of computation. Results and Conclusions With comparing with OptORF and OptFlux, two published target predicting algorithm for gene knockouts which also aiming at integrated network, two merits have been shown for RegKnock, i.e. absolutely accuracy and not a long time of computation. So RegKnock is a nice algorithm for predicting algorithm for gene deletions as for integrated network.