Application of Tabu search for metabolic flux analysis based on labeling balances.

摘要

Metabolic Flux Analysis (MFA) is a powerful tool to quantify the flux of biochemical reactions in a metabolic network. MFA consists of a mathematical model which is based on metabolite and labeling balances and optimization to minimize the difference between measurements and predictions. The combination of metabolite and labeling balances creates a nonconvex optimization problem with bilinear constraints, for which the existence of multiple local minima is a major difficulty. In this work, Tabu search, a stochastic optimization technique, is applied for the first time to find good model parameters for MFA problems. To test the effectiveness of this algorithm for MFA problems, fluxes of the central metabolism of Saccharomyces cerevisiae were computed. Solution times and accuracy of the computed fluxes were compared to those obtained by using a global approach, which requires time-consuming branching calculations, and to those obtained by an evolutionary method. A comparison shows the effectiveness of the algorithm for solving MFA problems to near global optimality. All three methods have equally valid results because the value of objective function for each method is within the error bound calculated for the objective function. The time required to solve the MFA problem for S.cerevisiae using Tabu search was found to be approximately 10 times faster than that required by previous methods. This performance is due to the ability of Tabu search to converge to the global optimum for this nonconvex example problem without the use of time-consuming bounding calculations. Parameter values for Tabu search were tuned by analyzing the sensitivity of the solution error and the convergence rate on the Tabu list length and the radius of immediate neighbor.