Optimization Methods in Metabolic Networks

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

To optimize metabolic networks engineers seek to mathematically model these networks, calculate yields of useful products, and pinpoint parts of the network that constrain the production of these products with the goal of increasing the efficiency of the metabolic networks. The hope is to develop better quality products at less cost. Optimization Methods in Metabolic Networksmain goal is to use the language and tools of mathematical programming to describe and solve frequently occurring problems in the analysis and redesign of metabolic networks.

Topics covered in the book start with a formal treatment of the relevant optimization problem class followed by application in the context of metabolic network analysis. The class of optimization problems becomes progressively more complex starting with Linear Programming and Mixed–Integer linear programming and concluding with Nonlinear and Mixed–Integer Nonlinear programming problems.

The book serves as a starting point for the students for more in–depth investigations of relevant techniques and concepts found in the cited literature. Optimization Methods in Metabolic Networks features: 

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 Provides source codes for examples presented on an accompanying website Includes Problems and Exercises for academic adopters 

Optimization Methods in Metabolic Networks can be used to introduce students with knowledge of metabolism to formal mathematical treatments of core computational tasks in metabolic networks or alternatively expose students with a mathematical programming background to metabolism. The hope is that the book will serve as a starting point for the students for more in–depth investigations of relevant techniques and concepts found in the cited literature.

Costas D. Maranas is a Donald B. Broughton Professor in the Department of Chemical Engineering at Pennsylvania State University. Dr. Maranas is a Fellow of the American Institute of Medical and Biological Engineering (AIMBE). In 2012 he was awarded the Penn State Engineering Alumni Society Outstanding Research Award.

Ali R. Zomorrodi obtained his PhD in Chemical Engineering at Penn State University under Costas D. Maranas and is currently a Postdoctoral Research Associate at Boston University. Dr. Zomorrodi′s areas of expertise include optimization–based modelling and model–driven analysis and redesign of biological networks.

CHAPTER 1: MATHEMATICAL OPTIMIZATION FUNDAMENTALS 1

1.1. Mathematical optimization and modeling 1

1.2. Basic concepts and definitions 9

1.3. Convex Analysis 12

1.3.1. Convex sets and their properties 12

1.3.2. Convex functions and their properties 15

1.3.3. Convex optimization problems 21

1.3.4. Generalization of convex functions 22

Exercises 23

References 24

CHAPTER 2: LINEAR PROGRAMMING AND DUALITY THEORY 27

2.1. Canonical and standard forms of an LP problem 27

2.1.1. Canonical form 28

2.1.2. Standard form 29

2.2. Geometric interpretation 30

2.3. Basic feasible solutions (BFS) 32

2.4. Simplex method 34

2.5. Duality in linear programming 42

2.5.1. Formulation of the dual problem 42

2.5.2. Primal–dual relations 44

2.5.3. The Karush–Kuhn–Tucker (KKT) optimality conditions 45

2.5.4. Economic interpretation of the dual variables 48

2.6. Nonlinear optimization problems that can be transformed into LP problems 53

2.6.1. Absolute values in the objective function 53

2.6.2. Minmax optimization problems with linear constraints 54

2.6.3. Linear fractional programming 55

Exercises 58

References 61

CHAPTER 3: FLUX BALANCE ANALYSIS AND LP PROBLEMS 62

3.1. Mathematical modeling of metabolism 63

3.1.1. Kinetic modeling of metabolism 63

3.1.2. Stoichiometric–based modeling of metabolism 63

3.2. Genome–scale stoichiometric models of metabolism 64

3.2.1. Gene–protein–reaction (GPR) associations 65

3.2.2. The biomass reaction 65

3.2.3. Metabolite compartments 66

3.2.4. Scope and applications 66

3.3. Flux balance analysis (FBA) 67

3.3.1. Cellular inputs, outputs and metabolic sinks 67

3.3.2. Component balances 68

3.3.3. Thermodynamic and capacity constraints 70

3.3.4. Objective function 71

3.3.5. FBA optimization formulation 72

3.4. Simulating gene knockouts 77

3.5. Maximum theoretical yield 78

3.5.1. Maximum theoretical yield of product formation 78

3.5.2. Biomass vs. product trade–off 79

3.6. Flux variability analysis (FVA) 82

Exercises 87

References 89

CHAPTER 4: MODELING WITH BINARY VARIABLES AND MILP FUNDAMENTALS 95

4.1. Modeling with binary variables 95

4.1.1. Continuous variable on/off switching 95

4.1.2. Condition–dependent variable switching 96

4.1.3. Condition–dependent constraint switching 96

4.1.4. Modeling AND relations 97

4.1.5. Modeling OR relations 98

4.1.6. Exact linearization of the product of a continuous and a binary variable 99

4.1.7. Modeling piecewise linear functions 100

4.2. Solving MILP problems 102

4.2.1. Branch–and–Bound procedure for solving MILP problems 103

4.2.2. Finding alternative optimal integer solutions 111

4.3. Efficient formulation strategies for MILP problems 112

4.3.1. Using the fewest possible binary variables 112

4.3.2. Fix all binary variables that do not affect the optimal solution 112

4.3.3. Group all coupled binary variables 112

4.3.4. Segregate binary variables in constraints rather than in the

objective function 113

4.3.5. Use tight bounds for all continuous variables 114

4.3.6. Introduce LP relaxation tightening constraints 114

4.4. Identifying minimal reaction sets supporting growth 117

Exercises 120

References 121

CHAPTER 5: THERMODYNAMIC ANALYSIS OF METABOLIC NETWORKS 123

5.1. Thermodynamic assessment of reaction directionality 123

5.2. Eliminating thermodynamically infeasible cycles 126

5.2.1. Cycles in cellular metabolism 126

5.2.2. Thermodynamically infeasible cycles (TICs) 127

5.2.3. Identifying reactions participating in thermodynamically

infeasible cycles 128

5.2.4. Thermodynamics–based metabolic flux analysis (TMFA) 128

5.2.5. Elimination of the thermodynamically infeasible loops by

applying the loop law 131

5.2.6. Elimination of the thermodynamically infeasible cycles

by modifying the metabolic model 133

Exercises 134

References 135

CHAPTER 6: RESOLVING NETWORK GAPS AND GROWTH

PREDICTION INCONSISTENCIES IN METABOLIC NETWORKS 137

6.1. Finding and filling network gaps in metabolic models 137

6.1.1. Categorization of gaps in a metabolic model 137

6.1.3. Gap finding 138

6.1.2. Gap filling 141

6.2. Resolving growth prediction inconsistencies 144

6.2.1. Quality metrics for quantifying the accuracy of metabolic models 145

6.2.2. Automated reconciliation of growth prediction inconsistencies

using GrowMatch 145

6.2.3. Resolution of higher–order gene deletion inconsistencies 149

6.3. Verification of model correction strategies 151

Exercises 153

References 153

CHAPTER 7: IDENTIFICATION AND CONSTRUCTION OF

PATHWAYS TO TARGET METABOLITES 156

7.1. Using MILP to identify shortest paths in metabolic graphs 156

7.2. Using MILP to identify non–native reactions for the production of a target

metabolite 162

7.3. Designing overall stoichiometric conversions 164

7.3.1. Determining the stoichiometry of overall conversion 164

7.3.2. Identifying reactions steps conforming to the identified overall stoichiometry 166

Exercises 172

Tables 172

References 173

CHAPTER 8: COMPUTATIONAL STRAIN DESIGN 176

8.1. Early computational treatment of strain design 177

8.2. OptKnock 179

8.2.1. Solution procedure for OptKnock 180

8.2.2. Improving the computational efficiency of OptKnock 187

8.2.3. Connecting reaction eliminations with gene knockouts 188

8.2.4. Impact of knockouts on the biomass–product tradeoff 188

8.3. OptKnock modifications 190

8.3.1. RobustKnock 190

8.3.2. Tilting the objective function 192

8.4. Other strain design algorithms 192

Exercises 194

References 195

CHAPTER 9: NLP Fundamentals 197

9.1. Unconstrained nonlinear optimization 197

9.1.1. Optimality conditions for unconstrained optimization problems 198

9.1.2. An overview of the solution methods for unconstrained

optimization problems 200

9.1.3. Steepest descent (Cauchy or gradient) method 201

9.1.4. Newton s method 202

9.1.5. Quasi–Newton methods 203

9.1.6. Conjugate gradients (CG) methods 204

9.2. Constrained nonlinear optimization 205

9.2.1. Equality–constrained nonlinear problems 205

9.2.2. Nonlinear problems with equality and inequality constraints 212

9.2.3. Karush–Kuhn–Tucker (KKT) optimality conditions 213

9.2.4. Sequential (Successive) quadratic programming (SQP) 215

9.2.5. Generalized reduced gradient (GRG) 219

9.3. Lagrangian duality theory 222

9.3.1. Relationships between the primal and dual problems 224

9.3.2. Solving the dual problem by cutting plane or outer–linearization method 225

Exercises 227

References 228

CHAPTER 10: NLP APPLICATIONS IN METABOLIC NETWORKS 230

10.1. Minimization of the metabolic adjustment (MOMA) 230

10.2. Incorporation of kinetic expressions in stoichiometric models 235

10.3. Metabolic flux analysis (MFA) 239

10.3.1. Definition of the relevant parameters and variables 240

10.3.2. Isotopomer mass balance 247

10.3.3. Optimization formulation for MFA 248

Exercises 251

References 253

CHAPTER 11: MINLP FUNDAMENTALS AND APPLICATIONS 256

11.1. An overview of the MINLP solution procedures 256

11.2. Generalized Benders Decomposition (GBD) 257

11.2.1. The primal problem in GBD 258

11.2.2. The master problem in GBD 259

11.2.3. Steps of GBD algorithm 263

11.3. Outer approximation (OA) 264

11.3.1. The primal problem 265

11.3.2. The master problem 266

11.3.3. Steps of the OA algorithm 270

11.4. Outer approximation with equality relaxation (OA/ER) 271

11.4.1. The master problem in OA/ER 273

11.5. Kinetic OptKnock (k–OptKnock) 274

11.5.1. k–OptKnock formulation 275

11.5.2. Solution procedure for k–OptKnock 277

Exercises 280

References 281