Automatic Design of Optimal Producers Using a Novel Approach Based on Elementary Flux Modes (EFMs), Minimal Cut Sets (MCSs), and Binary Integer Programing (BIP)

In recent years, microorganisms have been heavily used as cell factories to produce chemical commodities of interests. However, most of these microorganisms do not produced the desired substance with a sufficient yield. A main goal of metabolic engineering is to design host cells that generate the desired substances in an efficient and inexpensive way. So far, a number of numerical methods have been developed and successfully applied to achieve this goal, such as RobustKnock [1], elementary flux modes (EFMs) analysis [2], and minimal cut sets (MSCs) [3]. These methods are used to compute genetic intervention strategies that increase the production efficiency of the organism by (re-)routing available cellular resources towards favorable pathways which mainly/only produce the substance of interest.

In this work we present a novel approach to design an optimal producer which is based on EFMs and MCSs. EFMs are minimal pathways in steady-state which obey all reaction reversibility constraints. In the context of EFMs minimal means that the elimination of a single reaction participating in the pathway will completely block that pathway. This property is utilized by the concept of MCSs. MCSs are (genetic) rules that delete certain reactions and, hence, result in the removal of EFMs. The removal of EFMs inevitably causes the elimination of (some of) the network's functionality. Consequently, if MCSs are cleverly used then all unwanted functionality of a metabolic network can be removed while (most of) the desired functions are still operational.

The computation of EFMs and MCSs for larger metabolic networks is non-trivial and computational expensive. To this end, several methods for the efficient calculation of EFMs and MCSs have been proposed. EFMs are most often computed using a binary nullspace algorithm [4] which is based on the double description method [5]. MCSs are typically computed by utilizing the Berge algorithm [6, 7] or by the help of binary integer programs [8].

A major difficulty in using MCSs to optimize a production host is the classification of the EFMs: An EFM is either a wanted mode or it is an unwanted mode. Until now, this selection of EFMs had to be done manually before the computation of the MCSs was started. However, identifying the best classification is non-trivial, as there might be situations where slightly changing the sets of wanted and unwanted EFMs has only a minimal effect on the efficiency of the created microorganisms, but leads to a significant reduction in the number of reactions that have to be deleted. Here we present the formulation of a binary integer program (BIP) for the calculation of MCSs which automatically selects an optimal mode configuration and does no longer require a manual mode classification. Thus, given an engineering objective, our approach guarantees that no other intervention strategy will lead to a better strain.

We validated our new method using a metabolic core model of E. coli [9]. The model was applied to optimize the anaerobic production of ethanol from glucose. The used metabolic system contained 47 metabolites, 59 reactions and 5010 EFMs. The small size of the used E. colimodel allowed to easily classify the modes as wanted or unwanted and to identify all optimal solutions by other numerical methods [10]. We applied our new approach to this system and found that we obtained the same optimal solutions (with at least six deletions) as reported in [10], thereby proofing that our program works correctly. However, our algorithm also found a better design which only required five deletions without any negative impact on the predicted minimal and maximal specific productivity.

Next, we plan to use our algorithm to optimize a more detailed model of E. coli. This larger model is characterized by 72 metabolites, 71 reactions, and 429,276 EFMs. The size of the metabolic network prohibits a simple classification of the EFMs. We will use our tool to compute a minimal genetic intervention strategy that results in an optimized ethanol production.

In order to solve the BIP, we used the IBM ILOG CPLEX Optimizer. CPLEX is a commercial optimization tool box for which free academic licenses are available. Our implementation heavily relies on CPLEX' feature populate, which allows to efficiently calculate multiple solutions of an optimization problem with a single function call.

References

[1] Tepper N. and Shlomi T., Predicting metabolic engineering knockout strategies for chemical production: accounting for competing pathways, Bioinformatics, 26(4), 536-543, 2010

[2] Schuster S. and Hilgetag C., On elementary flux modes in biochemical reaction systems at steady state, J. Bio. Syst., 2, 165-182, 1994

[3] Haus U.-U., Klamt S. and Stephen T., Computing Knock-Out Strategies in Metabolic Networks, J. Comp. Bio., 15(3), 259-268, 2008

[4] Gagneur J and Klamt S., Computation of elementary modes: a unifying framework and the new binary approach, BMC Bioinformatics, 5(175), 1-21, 2004

[5] Fukuda K. and Prodon A., Double Description Method Revisited, Combinatorics and Computer Science, 91-111, 1996

[6] Berge C., Hypergraphs, Volume 45: Combinatorics of Finite Sets, North Holland, 1989

[7] Jungreuthmayer C., Beurton-Aimar M. and Zanghellini J., Fast Computation ofMinimal Cut Sets in Metabolic Networks with a Berge Algorithm that Utilizes Binary Bit Pattern Trees, IEEE/ACM Trans Comp Biol Bioinform, 2013

[8] Jungreuthmayer C. and Zanghellini J., Designing optimal cell factories: Integer programing couples elementary mode analysis with regulation, BMC Systems Biology, 6, 103, 2012

[9] Trinh C., Unrean P. and Srienc F., Minimal escherichia coli cell for the most efficient productino of ethanol from hexoses and pentoses, Appl. Env. Microbio., 74, 3634-3643, 2008

[10] Hädicke O. and Klamt S., CASOP: a computational approach for strain optimization aiming at high productivity, J. Biotech, 147, 88-101, 2010