Fast Enumeration of Smallest Metabolic Engineering Strategies in Genome-Scale Networks

Steffen Klamt1 and Axel von Kamp1

1Max Planck Institute for Dynamics of Complex Technical Systems, Magdeburg, Germany, klamt@mpi-magdeburg.mpg.de

One ultimate goal of metabolic network modeling is the rational modification of biochemical networks to optimize the bio-based production of certain compounds. Although several constraint- based optimization techniques have been proposed for this purpose, there is still a need for computational approaches allowing an effective systematic enumeration of efficient intervention strategies in large-scale metabolic networks.
Here we present the MCSEnumerator approach by which a large number of the smallest genetic intervention strategies (with fewest targets) can be readily computed in genome-scale metabolic models [1]. The algorithm builds upon an extended concept of Minimal Cut Sets (MCSs) which are minimal combinations of reaction (or gene) deletions leading to the fulfillment of a predefined intervention goal. It exploits the fact that smallest MCSs can be calculated as shortest elementary modes in a dual network and uses an improved procedure for shortest elementary-modes calculation. Recently, MCSEnumerator was extended to allow also for the computation of regulatory MCSs which are minimal combinations of reaction knockouts and up and downregulations enforcing a desired behavior (see Abstract of Mahadevan et al.).
Realistic application examples demonstrate that our algorithm is able to list thousands of the most efficient intervention strategies for various intervention problems in genome-scale networks. We used MCSEnumerator to compute strain designs for growth-coupled synthesis of different products by heterotrophic as well as photoautotrophic organisms. We found numerous new engineering strategies partially requiring fewer interventions and guaranteeing higher product yields than reported previously. In contrast to many other approaches, our method does not require the assumption of optimal growth since MCSs can be computed in such a way that they guarantee growth-coupled product synthesis for any growth rate. Generally, a broad spectrum of intervention problems can be considered: one only needs to provide a description of the desired and undesired behaviors (flux distributions) by means of linear inequalities. With this flexible definition, MCSEnumerator can also be employed for other purposes, e.g., for enumerating synthetic lethals.
In summary, the presented approach can quickly calculate a large number of smallest engineering strategies with neither network size nor the number of required interventions posing major challenges. Given its unprecedented speed and high flexibility in formulating intervention problems, we expect MCSEnumerator to become an important tool for Metabolic Engineering.

[1] von Kamp A and Klamt S (2014) Enumeration of smallest intervention strategies in genome-scale metabolic networks. PLoS Computational Biology 10: e1003378.