8 | metabolic engineering strategies I

Question 1

What is the motivation behind coupling product formation to growth?

Answer 1

• force cell to produce desired compound as by-product of growth
• → ensures production is evolutionarily stable.

Question 2

What is strong coupling in metabolic engineering?

Answer 2

KO strategy: product formation strongly coupled to growth (biomass production)
ensure any growth-supporting flux dist also produces product > threshold.

Question 3

What is weak coupling?

Answer 3

Product is only formed at the optimal growth flux, not necessarily under all conditions.

Question 4

What is the exhaustive KO strategy covered in lecture 8 on metabolic engineering?

Answer 4

• Try all possible subsets of knock-outs from the list of genes.
• Evaluate product yield or other objectives, solution = maximum of all maxima

Question 5

Write the LP for an exhaustive knock out enumeration.

Answer 5

For every subset 𝑇 ⊆ 𝐿:
max 𝑣_{𝑐ℎ𝑒𝑚𝑖𝑐𝑎𝑙}
s.t.
𝑁𝑣 =0
∀𝑗 ∈ 𝑇, 𝑣_𝑗= 0,
∀𝑖, 𝑖 ∉ 𝑇,𝑣_𝑖^𝑚𝑖𝑛 ≤ 𝑣_𝑖 ≤ 𝑣_𝑖^𝑚𝑎𝑥
𝑣_𝑏𝑖𝑜 ≥ 𝛼𝑧^∗
If we want sufficient high product yield to be at some level of biomass yield:
where 𝑧^∗ is the optimal growth.

Question 6

What additional constraint ensures viability in exhaustive knock-out tests?

Answer 6

v_bio ≥ α · z, where z is wild-type biomass flux

Question 7

What are the limitations of exhaustive knock-out search?

Answer 7

• Combinatorial explosion: infeasible for large gene lists
• Cannot scale to full genome-wide searches

Question 8

What is a bi-level optimization problem?

Answer 8

• One optimization problem (outer) depends on the solution of another (inner)
• I.e two nested optimizations
• The outer objective uses the result of the inner optimization

Question 9

Why do bi-level problems appear in metabolic engineering?

Answer 9

• The outer problem wants to maximize product formation (engineer)
• The inner problem responds by optimizing its own growth (cell)
• The engineering strategy must account for the internal optimization

Question 10

In OptKnock, what are the outer and inner problems?

Answer 10

• Outer: maximize v_target (e.g. product formation) by choosing KOs
• Inner: maximize v_bio (growth) given knock-outs

Question 11

How are knock-outs encoded in OptKnock?

Answer 11

• Binary variable y_i ∈ {0, 1}
• y_i = 1 → reaction is active
• y_i = 0 → reaction is knocked out → v_i = 0
• Use bounds: y_i * v_i^min ≤ v_i ≤ y_i * v_i^max

Question 12

What does the inner problem in a bi-level formulation depend on?

Answer 12

• The outer decision variables (e.g. knock-outs y)
• These change the feasible region for the inner problem
• The inner LP is parameterized by y

Question 13

What makes OptKnock a mixed-integer bi-level program?

Answer 13

• Outer layer includes binary variables y_i
• Inner problem is a linear program over flux variables v
• The feasible set for v depends on y

Question 14

What is OptKnock?

Answer 14

• A bi-level MILP to find knock-outs that couple growth and production
• Automates the search for knock-out designs

Question 15

How is the number of knock-outs restricted in OptKnock?

Answer 15

Add a constraint for K, the max allowed deletions: ∑(1−y_i) ≤ K

Question 16

What is the full program for OptKnock (Burgard et al. (2003) Biotech. & Bioeng.)

Answer 16

max over y: v_chemical
st:
max v_bio
st:
N v = 0
for all i ≤ 1 ≤ m, y_i · v_i^min ≤ v_i ≤ y_i · v_i^max
y_i ∈ {0, 1}
∑_i=1^m(1−y_i) ≤ K

Question 17

What does the inner problem in OptKnock represent?

Answer 17

The cell’s behavior: maximize biomass production given knock-outs

Question 18

What does the outer problem in OptKnock represent?

Answer 18

The engineer’s goal: maximize product formation by choosing which knock-outs to apply

Question 19

What assumptions does OptKnock make about the cell?

Answer 19

• The cell optimizes growth
• Product formation is only induced indirectly via knock-outs

Question 20

Why are bi-level problems difficult to solve?

Answer 20

• The inner problem changes with each outer decision
• You can’t just solve them separately
• to nesting, discrete nature of int vars → problem non-convex, combinatorial

Question 21

What does “combinatorial” mean in the context of bi-level optimization?

Answer 21

• refers to having to choose among many discrete combinations, eg KO sets
• Each combination may lead to a different inner solution
• possible combinations can grow very large - ‘combinatorial explosion’
• Can make problem hard to solve efficiently

Question 22

Why can’t bi-level problems be solved directly?

Answer 22

Inner LP depends on outer variables → standard MILP solvers unable to handle it directly.

Question 23

How can bi-level problems be solved in OptKnock?

Answer 23

Two approaches:
* By replacing the inner LP with its dual problem
* Apply Karush-Kuhn-Tucker (KKT) conditions (optimality) to connect primal, dual

Question 24

What are the KKT conditions used to solve bi-level problems?

(not so relevant ! )

Answer 24

• Stationarity
• Primal feasibility
• Dual feasibility
• Complementary slackness

Question 25

What is complementary slackness?

Answer 25

For each constraint: * If it's active, dual variable may be positive * If it's inactive, dual variable is zero

Question 26

What are mixed-integer linear programs (MILPs)?

Answer 26

LPs with some variables required to be integers (e.g. binary knock-out indicators)

Question 27

What is LP duality?

Answer 27

* Every LP has a dual problem * The dual variables represent the shadow prices of the constraints

Question 28

What is a shadow price in LP duality?

Answer 28

Each constraint in the primal has a shadow price. * = The value of a dual variable corresponding to a primal constraint * = how much objective function would improve if that constraint relaxed by 1 unit * AKA marginal value of a resource

Question 29

If you have n variables and m constraints in an LP, how many constraints will you have in its dual?

Answer 29

* m variables * n constraints

Question 30

What is the optimality property in LP duality?

Answer 30

Let 𝑥 be a feasible solution to a primal LP, and 𝜇 be a feasible solution to the dual LP. If 𝑐^𝑇𝑥 = 𝑏^𝑇𝜇 then 𝑥 and 𝜇 are optimal solutions to the primal and dual LPs, respectively.

Question 31

What is the strong duality property in LP duality?

Answer 31

* If primal has finite optimal solution, then so does its dual, and these values are equal. * ie max_𝑥 𝑐^𝑇𝑥 = min_𝜇 𝑏^𝑇𝜇 That means: * Solve the primal → get a value; Solve the dual → get a value. ✅ Both values are equal This only holds if: * The primal or dual has a feasible solution (satisfies all constraints) * The problem is bounded (no infinite solutions)

Question 32

How do you convert a primal LP into its dual (without Lagrangian)?

Answer 32

* Each constraint in the primal becomes a variable in the dual * Each variable in the primal becomes a constraint in the dual * The primal objective coefficients become RHS values in the dual constraints * The primal constraint matrix A is transposed in the dual

Question 33

In LP duality, what happens to ≥ constraints in the primal?

Answer 33

* They become ≤ constraints in the dual * Their corresponding dual variables must be ≥ 0

Question 34

What is the dual of this primal LP? min c^T x s.t. A_ineq x ≥ b_ineq x ≥ 0 A_eq x = b_eq

Answer 34

max b_ineq^T y₁ + b_eq^T y₂ s.t. A_ineq^T y₁ + A_eq^T y₂ ≤ c y₁ ≥ 0

Question 35

Why is LP duality useful in OptKnock?

Answer 35

* Allows removing inner LP, replacing with constraints involving dual variables * Converts the bi-level problem to a single-level MILP

Question 36

What are two approaches to flattening bi-level optimization problems?

Answer 36

* LP duality: replace the inner LP with its dual and enforce strong duality * KKT conditions: use stationarity, feasibility, and complementary slackness via the Lagrangian

Question 37

Do LP duality and KKT methods give the same solution for bi-level LPs?

Answer 37

* Yes, they both produce the same optimal result * They enforce optimality of the inner problem in different ways

Question 38

Do LP duality and KKT produce the same flattened single-level program?

Answer 38

No, the formulations differ * LP duality leads to a more compact and structured MILP * KKT-based reformulations are often larger and more complex

Question 39

What does it mean to "not use the Lagrangian approach" for duality?

Answer 39

* You should derive the dual using the standard LP rulebook, not calculus or KKT * Don’t introduce Lagrange multipliers * Just work structurally from constraint-to-variable transformation

Question 40

For a primal minimization problem: min c^Tx s.t. A x ≥ b x ≥ 0 What would be the key steps to formulate the dual?

Answer 40

Follow the standard duality principles in optimization. 1. Identify Primal Components: 2. Assign Dual Variables: 3. Formulate Dual Objective: 4. Formulate Dual Constraints:

Question 41

For a primal minimization problem: min c^Tx s.t. A x ≥ b x ≥ 0 What is the dual?

Answer 41

max_𝜇 4𝜇 s.t 𝜇 = 0 ------- Perplexity explanation: Original (primal) problem: Minimize y st y ≥ 0, x + y ≥ 4. **1. Identify Primal Components:** Variables: y≥0, x (unrestricted). Objective: Minimize y Constraints: One explicit constraint x+y≥4. **Assign Dual Variables:** Each primal constraint becomes a dual variable. Here, the constraint x+y≥4 corresponds to a dual variable λ≥0. **Formulate Dual Objective:** The dual objective is derived from the right-hand side of the primal constraint multiplied by λ: 4λ. **Formulate Dual Constraints:** For each primal variable, create a dual constraint based on its sign: For x (unrestricted): The coefficient of x in the primal constraint (1) forms an equality constraint in the dual: λ=0. For y (non-negative): The coefficient of y in the primal constraint (1) forms an inequality constraint: λ≤1. Combine Constraints: The dual constraints are λ=0, λ≤1, and λ≥0. **Dual Problem:** Maximize 4λ subject to λ=0, λ≥0, λ≤1. **Interpretation:** The only feasible solution for the dual is λ=0, yielding an optimal value of 0 This matches the primal optimal value y=0 (achieved when x≥4), demonstrating strong duality. **Summary:** The dual LP is trivial in this case because the unrestricted variable x forces λ=0. This ensures the primal and dual optimal values align, satisfying the duality theorems in linear programming.

Question 42

What is the simplified OptKnock reformulation/approximation from the exercise, often used computationally, which: * Turns the bilevel OptKnock problem into a single-level MILP * Focuses on minimizing the number of knockouts * Adds a small constant ε to soften knockouts ?

Answer 42

min ∑ y_i s.t. N v = 0 v_bio ≥ α · z* v_target ≥ β · w_target v ≥ 0 ∀ i:  (1 − y_i) · ε ≤ v_i  v_i ≤ (1 − y_i) · v_i^max + y_i · ε y ∈ {0,1}