Optimization Methods in Metabolic Networks (eBook)

Costas D. Maranas, Ali R. Zomorrodi (Autoren)

eBook Download: EPUB

2016 | 1. Auflage
288 Seiten
Wiley (Verlag)
978-1-119-18901-5 (ISBN)

Infos

Provides a tutorial on the computational tools that use mathematical optimization concepts and representations for the curation, analysis and redesign of metabolic networks 

• Organizes, for the first time, the fundamentals of mathematical optimization in the context of metabolic network analysis
• Reviews the fundamentals of different classes of optimization problems including LP, MILP, MLP and MINLP
• Explains the most efficient ways of formulating a biological problem using mathematical optimization
• Reviews a variety of relevant problems in metabolic network curation, analysis and redesign with an emphasis on details of optimization formulations
• Provides a detailed treatment of bilevel optimization techniques for computational strain design and other relevant problems

Costas D. Maranas is a Donald B. Broughton Professor in the Department of Chemical Engineering at Pennsylvania State University, USA. Dr. Maranas is a Fellow of the American Institute of Medical and Biological Engineering (AIMBE). In 2002 he was awarded by AIChE the Allan P. Colburn Award for Excellence in Publications by a Young Member of the Institute.

Ali R. Zomorrodi obtained his PhD in Chemical Engineering at Pennsylvania State University and is currently a Postdoctoral Research Associate at Boston University, USA. Dr. Zomorrodi's areas of expertise include optimization-based modeling and model-driven analysis of biological networks.

Textauszug

1
MATHEMATICAL OPTIMIZATION FUNDAMENTALS

This chapter reviews the fundamentals of mathematical optimization and modeling. It starts with a biological network inference problem as a prototype example to highlight the basic steps of formulating an optimization problem. This is followed by a review of some basic mathematical concepts and definitions such as set and function properties and convexity analysis.

1.1 MATHEMATICAL OPTIMIZATION AND MODELING

Mathematical optimization (programming) systematically identifies the best solution out of a set of possible choices with respect to a pre-specified criterion. The general form of an optimization problem is as follows:

where

• x is a N-dimensional vector referred to as, the vector of variables.
• S is the set from which the elements of x assume values. For example, S can be the set of real, nonnegative real or nonnegative integers. In general, variables in an optimization problem can be continuous, discrete (integer) or combinations thereof. The former is used to capture the continuously varying properties of a system (e.g., concentrations), whereas the latter is used for discrete decision making (e.g., whether or not to eliminate a reaction).
• f(x) is referred to as the objective function and serves as a mathematical description of the desired property of the system that should be optimized (i.e., maximized or minimized).
• and are constraints that must be satisfied as equalities or one-sided inequalities, respectively, and represent the feasible space of decision variables.

Any vector x that lies in S and satisfies h(x) and g(x) is called a feasible solution. In addition, if vector x minimizes (maximizes) the objective function, it is an optimal solution point to the optimization problem with an associated optimum solution value f(x). There are different classes of optimization problems depending on the (non)linearity properties of the objective function and constraints as well as the presence or absence of discrete (i.e., binary or integer) and/or continuous variables. Standard classes of optimization problems that generally require different solution techniques are as follows:

1. Linear programming (LP) problems involve a linear objective function f(x) and constraints h(x) and g(x) as well as only continuous variables x (Chapter 2).
2. Mixed-integer LP (MILP) problems are LP problems with some of the variables assuming only discrete values (Chapter 4).
3. Nonlinear programming (NLP) problems involve a nonlinear objective and/or some nonlinear constraints while all variables are continuous (Chapter 9).
4. Mixed-integer nonlinear programming (MINLP) problems are NLPs with some variables assuming only discrete values (Chapter 11).

Mathematical optimization has been used extensively to model a wide variety of problems in science and engineering. The development of an optimization formulation modeling a real-life problem often needs to be traversed multiple times as new data, modified problem descriptions and re-interpretations due to unanticipated optimal solutions come to play. This book concentrates on mathematical optimization applications for the analysis and redesign of biological systems, with a special emphasis on metabolic networks. Example 1.1 describes the basic steps for formulating a biological network inference task as an optimization problem.

Example 1.1

Given a set of genes and time-course DNA microarray data, formulate an optimization problem to identify the regulatory interaction coefficients between genes best explaining the observed gene expression levels. The schematic representation of time-course DNA microarray data for a sample gene interaction network is given in Figure 1.1.

Solution: A stepwise description is provided that codifies the sequence of tasks carried out for constructing the optimization model whose solution answers the problem.

Sets:

The first task in deriving the optimization formulation of a problem is defining a number of sets indicating the essential elements of the problem over which the parameters, variables and/or constraints are defined. Two sets can be defined for this problem as follows:

Here, N denotes the number of genes in the network.

Parameters:

Parameters (some of which are indexed over sets) encode the available data for the problem. The parameters that can be defined for this problem include the following:

• Xit: Expression level of gene at time point
• LBij: Lower bound on the interaction coefficient Cij (see the next section for the definition of Cij). Subscript j assumes values from set I.
• UBij: Upper bound on the interaction coefficient Cij.
• Δt: Sampling interval assuming that it is constant throughout the experimental DNA microarray data. For convenience we set Δt = 1.

Variables:

In contrast to parameters that have known values, variables typically only have initial values and/or lower/upper bounds, and their optimal values are obtained upon solving the optimization problem. As was the case with parameters, the introduction of sets allows for the grouping of multiple unknowns under the same variable name. For the problem in hand, we define two different categories of variables including a continuous and a discrete set of variables. The continuous variable set is defined as follows:

Cij: Interaction coefficient between genes and (effect of gene j on gene i), where

The binary variables yij capture the presence or absence of an interaction between genes i and j as follows:

Constraints:

Constraints are defined to enforce the conditions that need to be satisfied for the problem. A constraint for this example is needed to impose the assumption that the rate of change in the expression level of each gene is a linear function of the contributions of all genes in the network (including itself):

(1.1)

Here, we approximate the derivative terms with algebraic linear constraints using a finite (forward) difference approximation:

(1.2)

This implies that the identification of Cij requires solving the following under-determined set of linear equalities (note that the system of equations is under-determined because the number of pairwise interactions is much larger than the number of equations):

(1.3)

An additional constraint is introduced to model the presence or absence of an interaction for each pair of genes enforcing the definition of binary variables yij :

(1.4)

Observe that if yij is equal to zero, then Cij is forced to assume a value of zero; whereas when yij is equal to one, then Cij is free to assume any value between LBij and UBij.

Objective function:

Given that this is an under-determined system of equations, there can be infinite sets of Cij all satisfying the given constraints. Optimization can be used to select one out of the many feasible values for Cij that satisfies an optimality criterion. Here, we invoke the parsimony assumption whereby we accept as the most relevant solution the one that minimizes the total number of regulatory interactions. The total number of regulatory coefficients can be obtained by summation over all binary variables.

Optimization model (formulation):

By collecting all the constraints described earlier, the optimization problem is stated as follows:

(1.3)

(1.4)

The solution of this problem will provide the presence or absence of a regulatory interaction between each pair of genes in the network (captured by binary variable yij) and the magnitude and sign (i.e., activation vs. inhibition) of these interactions (captured by the continuous variables Cij).

Exploring trade-offs between prediction error and model complexity:

It is important to emphasize that the solution of an optimization problem always needs to be scrutinized in terms of both mathematical accuracy and the relevance to the problem. For example, a key concern for this example is whether the obtained coefficients indeed capture biologically relevant interactions or are simply artifacts of the parameter fitting process. In addition, one might be interested to know whether the identified regulatory coefficients are unique or there exists alternate optimal sets. Optimization provides ways to address these types of questions by trading-off accuracy versus model complexity (i.e., parsimony in this case). This can be accomplished for this example by exploring how the total number of non-zero Cij’s decrease upon allowing for some degree of violation in the equality constraints. Introducing slack variables and for Constraint 1.3 allows for both positive and negative departures from...

Produkt-Details

• Erscheint lt. Verlag: 5.1.2016
• Sprache: englisch
• Themenwelt: Naturwissenschaften ► Biologie
• Themenwelt: Naturwissenschaften ► Chemie ► Technische Chemie
• Themenwelt: Technik ► Umwelttechnik / Biotechnologie
• Schlagworte: biochemical engineering • Biochemie • Biochemische Verfahrenstechnik • biomedical engineering • Biomedizintechnik • Biowissenschaften • Cell & Molecular Biology • chemical engineering • Chemische Verfahrenstechnik • Life Sciences • Molecular Bioengineering • Molekulares Bioengineering • Zellbiologie • Zell- u. Molekularbiologie
• ISBN-10: 1-119-18901-2 / 1119189012
• ISBN-13: 978-1-119-18901-5 / 9781119189015