(475d) A Novel Outer Approximation Algorithm for the Global Optimization of Metabolic Networks

The study of complex biological systems requires the integration of experimental and computational research by adopting a systems biology approach. Here, computational biology plays a major role by developing modeling tools that aim to provide a powerful foundation from which to address critical scientific questions. In this general context, we distinguish between different applications for which specific tools able to deal with the associated complexity are required. One of these applications, the optimization of metabolic networks, has recently emerged as a very important goal in biotechnology [2-3, 5-6, 9].

In recent years, the use of genetic manipulation techniques has led to significant improvements in the production of certain biochemical products. However, in most cases mutation and selection of new processes has been made in a proof-and-error basis [10], which can lead, at the best, to local optimal solutions. As actual biological processes are operating far from their global (theoretical) optimum, one expects that they could be further improved if quantitative design principles for enzyme activities were provided by a more rational approach like optimization. This optimization is known as engineering design and consists of, given a model, finding the appropriate changes in the gene expressions so that a certain objective function (typically a flow) is optimized.

One of the key steps in this approach is the selection of the appropriate mathematical model among the different representations available. Among them, representations that result from the combination of linear stoichiometric descriptions of the network and nonlinear empirical equations expressing the velocity show a good compromise between accuracy and simplicity. Particularly, in this group we find the S-System and General Mass Action (GMA) representations, which have been shown to capture in an efficient way the non-linearities associated with the regulatory processes of the networks while showing linear properties in the logarithmic space [10]. GMA models only differ from S-System models in the way in which the branching points are handled. In GMA models, each process in a branching point is approximated separately, while in S-System models, all the input and output flows are collected and modeled as just two contributions.

S-Systems models based on the power-law formalism were first used in metabolic optimization problems by Voit [11]. In S-Systems models, a logarithmic transformation is enough to obtain a linear representation providing a convenient framework for linear optimization techniques [1, 7, 11]. This is not possible with GMA models. The complexity in solving these models stems from their non-convexities, which give rise to multiple local optima in which standard optimization packages may get trapped during the search. Hence, advanced global optimization methods are required to converge to the global optimum of the problem. These methods are based on calculating valid lower and upper bounds on the global solution of the problem. These bounds are gradually tightened until a desired optimality criterion is satisfied.

Unfortunately, there are currently very few methods available for the global optimization of GMA models [8, 10]. The main drawback of these existing methods is that they provide solutions with large optimality gaps. Thus, there is still room for improvement to achieve the performance required by this type of studies.

Specifically, in this work we present a novel algorithm to globally optimize metabolic networks that are modeled via the GMA representation. The optimization method we propose, which is based on the works by Polisetty et al. [10] and Bergamini and coworkers [4], makes use of an outer-approximation strategy. In the approach presented, the original problem is decomposed into two problems at two different hierarchical levels: a master problem and a slave problem. The master problem takes the form of a convex mixed-integer linear programming (MILP problem) and is obtained by convexifying the original non-convex NLP formulation. This MILP problem is a relaxation (i.e., it overestimates the original search space) of the original non-convex problem, and hence provides a valid upper bound on its global solution. The output of this master problem is used to set bounds for some of the variables in the non-convex slave problem, which is locally optimized to obtain a lower bound on its global optimum. The relaxation of the master problem is then gradually tightened and the whole procedure is repeated until a termination criterion is satisfied.

The capabilities of our strategy have been illustrated through its application to the optimization of (1) the ethanol production in the fermentation of Saccharomyces Cerevisiae and (2) the citric acid synthesis rate produced by Aspergillus niger. GMA models for these two systems can be found in [10]. The method presented provided solutions with much lower optimality gaps than those reported in the literature. Furthermore, our strategy was shown from these numerical examples to perform much better than BARON, the state of the art solver for global optimization, in terms of optimality gap and computation time.

References

[1] Alvarez-Vasquez F, Canovas M, Iborra JL, Torres NV: Modeling, optimization and experimental assessment of continuous L-(-)-carnitine production by Escherichia coli cultures. Biotechnol Bioeng 2002, 80(7):794?805.

[2] Bailey J, Birnbaum S, Galazzo J, Khosla C, Shanks J: Strategies and challenges in metabolic engineering. Ann. NY Acad. Sci. 1990, 589:1?15.

[3] Banga JR: Optimization in computational systems biology. BMC Syst Biol 2008, 2:47.

[4] Bergamini ML, Aguirre P, Grossmann I: Logic-based outer approximation for globally optimal synthesis of process networks. Computers and Chemical Engineering 2005, 29:1914?1933.

[5] Cameron D, Chaplen F: Developments in metabolic engineering. Curr. Opin. Biotechnol. 1997, 8:175?180.

[6] Cameron D, Tong J: Cellular and metabolic engineering: an overview. Appl.Biochem.Biotechnol. 1993, 38:105?140.

[7] Marin-Sanguino A, Torres NV: Optimization of biochemical systems by linear programming and general mass action model representations. Math Biosci 2003, 184(2):187?200.

[8] Marin-Sanguino A, Voit EO, Gonzalez-Alcon C, Torres NV: Optimization of biotechnological systems through geometric programming. Theor Biol Med Model 2007, 4:38.

[9] Mendes P, Kell D: Making cells work - metabolic engineering for everyone. Trends Biotechnol. 1996, 15:6?7.

[10] Polisetty PK, Gatzke EP, Voit EO: Yield optimization of regulated metabolic systems using deterministic branch-and-reduce methods. Biot Bioeng 2008, 99(5):1154?69.

[11] Voit EO: Optimization in integrated biochemical systems. Biotechnol Bioeng 1992, 40(5):572?82.