Optimization Methods in Metabolic Networks

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.

• Preface xiii1 Mathematical Optimization Fundamentals 11.1 Mathematical Optimization and Modeling 11.2 Basic Concepts and Definitions 71.2.1 Neighborhood of a Point 71.2.2 Interior of a Set 71.2.3 Open Set 81.2.4 Closure of a Set 81.2.5 Closed Set 81.2.6 Bounded Set 81.2.7 Compact Set 81.2.8 Continuous Functions 91.2.9 Global and Local Minima 91.2.10 Existence of an Optimal Solution 91.3 Convex Analysis 101.3.1 Convex Sets and Their Properties 101.3.2 Convex Functions and Their Properties 131.3.3 Convex Optimization Problems 191.3.4 Generalization of Convex Functions 20Exercises 20References 222 LP and Duality Theory 232.1 Canonical and Standard Forms of an LP Problem 232.1.1 Canonical Form 242.1.2 Standard Form 242.2 Geometric Interpretation of an LP Problem 262.3 Basic Feasible Solutions 282.4 Simplex Method 302.5 Duality in Linear Programming 352.5.1 Formulation of the Dual Problem 352.5.2 Primal‐Dual Relations 382.5.3 The Karush‐Kuhn‐Tucker (KKT) Optimality Conditions 392.5.4 Economic Interpretation of the Dual Variables 402.6 Nonlinear Optimization Problems that can be Transformed into LP Problems 452.6.1 Absolute Values in the Objective Function 452.6.2 Minmax Optimization Problems with Linear Constraints 462.6.3 Linear Fractional Programming 47Exercises 49References 503 Flux Balance Analysis and LP Problems 533.1 Mathematical Modeling of Metabolism 543.1.1 Kinetic Modeling of Metabolism 543.1.2 Stoichiometric-Based Modeling of Metabolism 543.2 Genome‐Scale Stoichiometric Models of Metabolism 553.2.1 Gene–Protein–Reaction Associations 553.2.2 The Biomass Reaction 563.2.3 Metabolite Compartments 573.2.4 Scope and Applications 573.3 Flux Balance Analysis (FBA) 573.3.1 Cellular Inputs, Outputs and Metabolic Sinks 583.3.2 Component Balances 593.3.3 Thermodynamic and Capacity Constraints 603.3.4 Objective Function 613.3.5 FBA Optimization Formulation 623.4 Simulating Gene Knockouts 673.5 Maximum Theoretical Yield 683.5.1 Maximum Theoretical Yield of Product Formation 683.5.2 Biomass vs. Product Trade‐Off 693.6 Flux Variability Analysis (Fva) 713.7 Flux Coupling Analysis 73Exercises 77References 784 Modeling with Binary Variables and MILP Fundamentals 814.1 Modeling with Binary Variables 834.1.1 Continuous Variable On/Off Switching 834.1.2 Condition‐Dependent Variable Switching 834.1.3 Condition‐Dependent Constraint Switching 844.1.4 Modeling AND Relations 844.1.5 Modeling OR Relations 864.1.6 Exact Linearization of the Product of a Continuous and a Binary Variable 864.1.7 Modeling Piecewise Linear Functions 874.2 Solving Milp Problems 894.2.1 Branch‐and‐Bound Procedure for Solving MILP Problems 904.2.2 Finding Alternative Optimal Integer Solutions 974.3 Efficient Formulation Strategies for Milp Problems 974.3.1 Using the Fewest Possible Binary Variables 974.3.2 Fix All Binary Variables that do not Affect the Optimal Solution 984.3.3 Group All Coupled Binary Variables 984.3.4 Segregate Binary Variables in Constraints Rather than in the Objective Function 984.3.5 Use Tight Bounds for All Continuous Variables 994.3.6 Introduce LP Relaxation Tightening Constraints 994.4 Identifying Minimal Reaction Sets Supporting Growth 102Exercises 104References 1065 T hermodynamic Analysis of Metabolic Networks 1075.1 Thermodynamic Assessment of Reaction Directionality 1075.2 Eliminating Thermodynamically Infeasible Cycles (TICs) 1095.2.1 Cycles in Cellular Metabolism 1095.2.2 Thermodynamically Infeasible Cycles 1105.2.3 Identifying Reactions Participating in TICs 1115.2.4 Thermodynamics‐Based Metabolic Flux Analysis 1115.2.5 Elimination of the TICs by Applying the Loop Law 1135.2.6 Elimination of the TICs by Modifying the Metabolic Model 115Exercises 116References 1176 Resolving Network Gaps and Growth Prediction Inconsistencies in Metabolic Networks 1196.1 Finding and Filling Network Gaps in Metabolic Models 1196.1.1 Categorization of Gaps in a Metabolic Model 1196.1.2 Gap Finding 1206.1.3 Gap Filling 1236.2 Resolving Growth Prediction Inconsistencies 1266.2.1 Quality Metrics for Quantifying the Accuracy of Metabolic Models 1276.2.2 Automated Reconciliation of Growth Prediction Inconsistencies Using GrowMatch 1276.2.3 Resolution of Higher‐Order Gene Deletion Inconsistencies 1306.3 Verification of Model Correction Strategies 132Exercise 133References 1337 Identification of Connected Paths to Target Metabolites 1377.1 Using Milp to Identify Shortest Paths in Metabolic Graphs 1377.2 Using Milp to Identify Non‐Native Reactions for the Production of a Target Metabolite 1427.3 Designing Overall Stoichiometric Conversions 1447.3.1 Determining the Stoichiometry of Overall Conversion 1447.3.2 Identifying Reactions Steps Conforming to the Identified Overall Stoichiometry 146Exercises 151References 1518 Computational Strain Design 1558.1 Early Computational Treatment of Strain Design 1568.2 Optknock 1588.2.1 Solution Procedure for OptKnock 1598.2.2 Improving the Computational Efficiency of OptKnock 1648.2.3 Connecting Reaction Eliminations with Gene Knockouts 1658.2.4 Impact of Knockouts on the Biomass vs. Product Trade‐Off 1658.3 Optknock Modifications 1678.3.1 RobustKnock 1678.3.2 Tilting the Objective Function 1688.4 Other Strain Design Algorithms 168Exercises 170References 1719 N LP Fundamentals 1739.1 Unconstrained Nonlinear Optimization 1739.1.1 Optimality Conditions for Unconstrained Optimization Problems 1749.1.2 An Overview of the Solution Methods for Unconstrained Optimization Problems 1769.1.3 Steepest Descent (Cauchy or Gradient) Method 1769.1.4 Newton’s Method 1779.1.5 Quasi‐Newton Methods 1789.1.6 Conjugate Gradients (CG) Methods 1799.2 Constrained Nonlinear Optimization 1809.2.1 Equality‐Constrained Nonlinear Problems 1809.2.2 Nonlinear Problems with Equality and Inequality Constraints 1869.2.3 Karush–Kuhn–Tucker Optimality Conditions 1879.2.4 Sequential (Successive) Quadratic Programming 1899.2.5 Generalized Reduced Gradient 1929.3 Lagrangian Duality Theory 1959.3.1 Relationships between the Primal and Dual Problems 196Exercises 196References 19710 N LP Applications in Metabolic Networks 19910.1 Minimization of the Metabolic Adjustment 19910.2 Incorporation of Kinetic Expressions in Stoichiometric Models 20310.3 Metabolic Flux Analysis (Mfa) 20610.3.1 Definition of the Relevant Parameters and Variables 20810.3.2 Isotopomer Mass Balance 21410.3.3 Optimization Formulation for MFA 215Exercises 218References 22011 Minlp Fundamentals and Applications 22311.1 An Overview of the Minlp Solution Procedures 22411.2 Generalized Benders Decomposition 22411.2.1 The Primal Problem 22511.2.2 The Master Problem 22611.2.3 Steps of the GBD Algorithm 22911.3 Outer Approximation 23011.3.1 The Primal Problem 23111.3.2 The Master Problem 23111.3.3 Steps of the OA Algorithm 23511.4 Outer Approximation With Equality Relaxation 23611.4.1 The Master Problem 23711.5 Kinetic Optknock 23811.5.1 k‐OptKnock Formulation 23911.5.2 Solution Procedure for k‐OptKnock 240Exercises 242References 243Appendix A 245Index 257