Exam | essay questions

Question 1

Part 3 | Essay question (10 pts)

Provide a brute-force algorithm to determine knock-outs that maximize a given flux (5 points).

Provide a description of optKnock and discuss the difference to the previous algorithm (5 points).

(2020_2, )

Answer 1

Brute-force

Given metabolic network, product of interest, and a list of reactions, 𝐿, to be knocked-out:

• Enumerate every set T ⊆ L for all poss combos of rxn knock-outs
• For each combination:
  
  • Solve FBA with the LP:
    max_v c^Tv
    s.t.:
    Nv = 0 (steady state)
    ∀ j ∈ T: v_j = 0
    ∀ i ∉ T: v_i^min ≤ v_i ≤ v_i^max
  • Record target flux value for each case
• Return set of knock outs that yielded max target flux

Pros: Simple, exhaustive
Cons: Computationally expensive (combinatorial explosion)

OptKnock and difference to brute-force (5 pts)

OptKnock (Burgard et al., 2003):

• uses binary variables y_i to model KOs (y_i = 0 means KO)
• finds KOs to force cell to couple growth with production of desired metabolite.
• Bi-level optimization
• Outer problem: Select KOs to maximize flux of chemical of interest
• Inner problem: Predict resulting flux distribution by solving FBA (maximize growth rate)
• Typically solved by replacing inner LP with its dual and enforcing strong duality, or with a Karush-Kuhn-Tucker-based approach using the conditions of stationarity, primal and dual feasibility, and complementary slackness) yielding single-level MILP
• full LP
  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

Key differences:

Feature | Brute-force | OptKnock

Approach | Exhaustive enumeration | Optimization-based
Model structure | Multiple LPs | One MILP
Scalability | Poor | Much more efficient
Coupling | Not enforced | Growth–prdct coupling enforced
Insight | Post-hoc analysis | Predictive design tool

Question 2

Part 3 | Essay question (10 pts)

Explain what information is provided by flux variability analysis and to what end can it be used (2 points).

Provide the mathematical program for flux variability analysis (5 points). Is there a relationship between flux variability and flux coupling analysis? If so, specify it mathematically (3 points).

(2020_test, 2018_test)

Answer 2

Explain what information is provided by FVA & to what end can it be used (2 points)

Info provided:
- Feasible flux ranges at steady state → blocked reactions
- Operational flux ranges when enforcing both steady state and optimal objective (e.g., biomass ≥ α·z^*) → robustness

can be used to:
- classify rxns according to allowable flux span at optimum biomass (coupling to objective → hard-/partially-/not-coupled or blocked → blocked, essential, flexible?),
- identify alternative optima by fixing some fluxes eg to min/max operational values found in FVA and then do FBA → Compare different conditions (e.g., carbon source) or objectives, focus on reactions with non-overlapping ranges …
- for flux sampling to characterise distribution of flux ranges → classifcation reactions based on shape of distribution / based on correlation between 2 reaction fluxes
- support FCA
- needed for problems such as optKnock, …

Provide the mathematical program for flux variability analysis (5 points)

For each reaction R_i, solve:

min(max)_𝑣 𝑣_𝑖
s.t.
𝑁𝑣 = 0
∀𝑖, 1 ≤ 𝑖 ≤ 𝑚, 𝑣_𝑖^𝑚𝑖𝑛 ≤ 𝑣_𝑖 ≤ 𝑣_𝑖^𝑚𝑎𝑥
𝑧 (=c^Tv eg for biomass) ≥ 𝛼𝑧^∗ (optional: to restrict to optimal/near-optimal growth)

Is there a relationship between flux variability and flux coupling analysis? If so, specify it mathematically (3 points)
FCA builds on FVA:

• FVA defines the feasible and operational flux region
• FCA uses that region to analyze flux ratios
• The relationship between FVA and FCA can be mathematically expressed as:
  𝑣_𝑖^min / ⁡𝑣_𝑗^max⁡ ≤ 𝑣_𝑖/𝑣_𝑗 ≤ 𝑣_𝑖^max/𝑣_𝑗^min
• If R_i ⇔ R_j (full coupling), then:  v_i^min/v_j^min = v_i^max/v_j^max = const
• So: fully coupled reactions have proportional min/max fluxes across FVA
• and other relationships for other types of coupling

Resemblance of the LPs:

• Both use:
  
  • Steady-state constraint (N·v = 0)
  • Capacity constraints of flux bounds (v_min ≤ v ≤ v_max)
• FCA transforms a ratio (e.g. v_i / v_j) into an LP by rescaling the problem space via Charnes-Cooper transformation → resulting program resembles FVA
• Difference:
  
  • FVA: finds min/max for individual fluxes / FCA: finds min/max of a ratio between fluxes
  • FCA is solved in a scaled space, not the original flux space

Question 3

Part 3 | Essay question (10 pts)

Clearly define and mathematically specify Gibbs free energy of a reaction (2 points).

Use the definition to specify the constraints in thermodynamic metabolic flux analysis (TMFA) (8 points).

(2020_test )

Answer 3

Clearly define and mathematically specify Gibbs free energy of a reaction (2 points)

Gibbs free energy is a measure of chemical energy affected by two driving
forces: ∆𝐻 and ∆𝑆

All chemical systems (and thus, reactions, too) tend towards states of minimum Gibbs free energy.

Gibbs free energy change of reaction i:
ΔG_i = ΔG_i^° + RT · ∑_j S_ji ln(x_j) = ΔG_i^° + RT · N^Tz (with z = ln(x))

Tells whether a reaction is thermodynamically favorable:   
- If ΔG_i < 0 → forward reaction is feasible
- If ΔG_i > 0 → backward reaction is feasible

Specify the constraints in thermodynamic metabolic flux analysis (TMFA) (8 points)

Formulation (MILP):

Objective: max_{v, ΔG, z} c^Tv

Subject to:

• Steady-state: N·v = 0
• Thermodynamic constraints:
  ∀i: ΔG_i − K + K·y_i < 0
  ΔG_i = ΔG_i^° + RT · N^Tz
• Metabolite concentrations:
  ln(x_min) ≤ z ≤ ln(x_max)
• Directionality constraints with indicator variables y_i ∈ {0,1}:
  ε·y_i ≤ v_i ≤ y_i·v_i,max

Variables:

• v: flux vector
• ΔG: Gibbs free energy per reaction
• z: log metabolite concentrations
• y_i: binary variable for directionality

Notes:

• This is a mixed-integer linear program (MILP)
• K is a large constant for constraint relaxation

Question 4

Part 4 - Synthesis (15 points)

(15 points) Provide a mathematical program that predicts a parsimonious steady- state flux distribution under the assumption that the modelled system optimizes biomass yield and the total flux through each metabolic pool is provided as input (15 points).

(2020_test)

Answer 4

Mathematical Program: Parsimonious Flux Distribution with Pool Constraints (15 pts)

Let:

• z^* = optimal biomass flux / growth rate (from FBA)
• f_k = total flux through pool k (provided)
• P_k = sets of reactions in pool k

LP:

• min_v ∑_i |v_i| [=min_v ∑_i v_i⁺ + v_i^-]
  s.t.
  
  • Nv = 0
  • v_bio ≥ α · z^*  || Enforce optimal biomass
  • v^min ≤ v ≤ v^max || capacity constraints
  • v_i = v_i⁺ - v_i^- || abs value trick
  • v_i⁺, v_i^- ≥0 || abs value trick
  • ∀ k:  ∑_{i ∈ Pk} v_i = f_k  // Pool flux = input

Question 5

Part 5 - Extra credit question (10 points)

Specify a mathematical program that minimizes the total flux sum over all metabolic pools at steady state (8 points) The flux sum around a metabolic pool is the sum of all fluxes that contribute to the synthesis and degradation of the metabolite. Provide an illustration on a small example metabolic network (2 points).

(2020_test)

Answer 5

see sheet.

Question 6

Part 3 | Essay question (10 pts)

MOMA vs ROOM
Provide a conceptual comparison between MOMA and ROOM. Mention key Pseudocode lines and difference betw iple of a quadratic function (3), menti on what it was related to in the lecture

(2024_1)

Define ROOM and mathematical part behind. Why does room take only one path near the break point instead of 2 paths like MOMA?

(2025_1)

Answer 6

SEE WRITTEN PAGE FOR MORE

**MOMA and ROOM
Provide a conceptual comparison between MOMA and ROOM(5pts). Precisely describe the mathematical programs underlying the two approaches (5pts). **

• both enable knock out and comparison of mutants to wild type
• both don’t explicitly optimize biomass

MOMA:

• flux distribution in mutant should be as close as possible to that in wild type -> distance between optima (minimize eucledian distance)
• Quadratic Program by minimizing eucledian distanze

→ good for transient stage

ROOM:

• regulary changes in genetic, gene knock outs are minimized
• flux has to show significant change
• bounds based on bounds of wild type and relative changes and sensitivity bound
• MILP
• → good for postadaption stage
  → improves correlation of fluxes compared to MOMA

Question 7

Part 3 | Essay question (10 pts)

Charnes Cooper Transformation
Show it in FCA and its application

(2025_1, 2024_1, 2018_test similar)

Answer 7

SEE SHEET

Question 8

Part 3 | Essay question (10 pts)

Optknock and bilevel programming
Compare two approaches to solve a bilevel linear program
Provide a precise description of how bilevel programming is used for metabolic engineering

(2024_1, 2018_test)

Answer 8

Two approaches
KKT and Dual Problems
- solve binary program by converting it into single level

KKT
- take lagrangian for objective and constraints
- calculate gradient for langrangian
- stationary optimum is at gradientL(x,l)=0
- inequality optimization needs added binding constraint
Dual Problems
- convert primal LP into Dual LP by rearranging the langrangian to new LP
- optimal solution a optimal for primal and dual
In metabolic engineering
- increasement of product of interest possible in combination with knockout while maintaining optimal growth
OptKnock
- Suggests gene deletion strategies leading to the overproduction of a pre-specified metabolite using the provided metabolic model. A nested optimization framework identifies the gene deletions by coupling the production of the desired product with biomass formation.

Question 9

Part 4 - Synthesis (15 points)

You have a metabolite Mi. Get the flux range for all of fluxes for a specific metabolite. Extend the formulation(?) of fluxes by making it thermodynamically feasible (?). Something related to this was asked in the exam

(2024_1)

Answer 9

question a bit unclear

but use FBA and TMFA?

(google doc said pFBA, minmax, TMFA but not sure why those unless there was more to question)

see TMFA below and also needs extension to eliminate SBCs! see other q on this !!!

(TMFA)

Formulation (MILP):

Objective: max_{v, ΔG, z} c^Tv

Subject to:

• Steady-state: N·v = 0
• Thermodynamic constraints:
  ∀i: ΔG_i − K + K·y_i < 0
  ΔG_i = ΔG_i^° + RT · N^Tz
• Metabolite concentrations:
  ln(x_min) ≤ z ≤ ln(x_max)
• Directionality constraints with indicator variables y_i ∈ {0,1}:
  ε·y_i ≤ v_i ≤ y_i·v_i,max

Variables:

• v: flux vector
• ΔG: Gibbs free energy per reaction
• z: log metabolite concentrations
• y_i: binary variable for directionality

Notes:

• This is a mixed-integer linear program (MILP)
• K is a large constant for constraint relaxation
• TMFA can be extended to eliminate SBCs eliminates thermodynamically infeasible loops

Question 10

Part 5 - Extra credit question

You have specific nutrient given and how will you maximise the yield of a given metabolite with the help of specific nutrient

(2024_1)

Answer 10

optStrain

see sheet

Question 11

Part 3 | Essay question (10 pts)

LP of OptReg (8 points) and describe how each of the intervals can be obtained using the LP (2 points).

(2024_2,

Answer 11

(8 pts) LP for OptReg:

Objective:

• Maximize biochemical production while maintaining growth
  max_{y^k, y^d, y^u, v} v_biochemical − ε · ∑_j v_j

Subject to:

• Steady state: ∑_j S_ij · v_j = 0 for all i ∈ N
• Growth + uptake constraints:
  v_ATP ≥ v_{ATP_maint}
  v_glc = 10 mmol/gDW·h
  v_biomass ≥ 0.01 · v_biomass^max
• KO bounds:
  v_j^min · y_j^k ≤ v_j ≤ v_j^max · y_j^k
• Up-regulation bounds:
  [(v_j,L⁰ · (1−C) + v_j^min · C) · (1−y_j^d)] + v_j^max · y_j^d ≥ v_j
• Down-regulation bounds:
  v_j ≥ [(v_j,U⁰ · (1−C) + v_j^max · C) · (1−y_j^u)] + v_j^min · y_j^u
• Consistency constraints:
  (1−y_j^k) + (1−y_j^d) + (1−y_j^u) ≤ 1  (only one manipulation per rxn)
    ∑_j (1−y_j^k + 1−y_j^d + 1−y_j^u) ≤ L  (limit total edits)
• Binary variables: y_j^k,d,u ∈ {0,1}

(2 pts) Intervals explained:

• Knock-outs:
  y_j^k = 0 → v_j = 0
  y_j^k = 1 → normal bounds: v_j^min ≤ v_j ≤ v_j^max
• Down-regulation:
  y_j^d = 0 → tighter upper bound
  y_j^d = 1 → normal bounds
• Up-regulation:
  y_j^u = 0 → tighter lower bound
  y_j^u = 1 → normal bounds

Each constraint adjusts the allowable flux range depending on whether that reaction is targeted for a KO, down-, or up-regulation.

Question 12

Part 3 | Essay question (10 pts)

Define SBC and illustrate (3 points). Present a constraint based approach that generates steady state flux distribution that does not include SBC (7 points).

(2024_2, 2025_1)

Answer 12

Define SBC and illustrate (3 points)
✅ Definition:
An SBC (Stoichiometrically Balanced Cycle) is a thermodynamically infeasible reaction loop in a metabolic network.

• It is a steady-state flux distribution involving only internal reactions.
• It does not result in net production or consumption of any metabolite.
• SBCs do not violate mass balance or linear constraints.
• However, they violate the laws of thermodynamics, because they can carry arbitrarily large fluxes in a closed loop without any input or output.

✅ Illustration (from slide)

• A → B → C → A, each with flux = 1000
• ΔG°_f(A) < ΔG°_f(B) < ΔG°_f(C) < ΔG°_f(A)
  → Leads to a thermodynamic contradiction
• This closed cycle creates a perpetual motion loop

Present a constraint-based approach to eliminate SBCs (7 points)
To generate steady-state flux distributions without SBCs, we use a thermodynamic constraint-based method:
✅ Step 1: Remove exchange reactions
Let:

• N_int be the stoichiometric matrix with only internal reactions
• Compute P_int = null(N_int), i.e., the null space of internal reactions

A network without SBCs must satisfy:

• P_int^T G = 0, where G is the vector of reaction Gibbs energies

✅ Step 2: Introduce a sign-consistent variable G_i
Let each reaction i be associated with a number G_i, such that:

• sign(G_i) = sign(ΔG_i)
• Enforce: v_i · G_i ≤ 0
  (Flux can only go in the direction of negative ΔG)

✅ Step 3: Binary indicator variable a_i
Introduce a binary variable a_i:

• a_i = 1 if v_i > 0
• a_i = 0 if v_i < 0

Use these to encode:
vi,min⁡(1−ai)≤vi≤vi,max⁡aiv_{i,\min}(1 - a_i) ≤ v_i ≤ v_{i,\max}a_ivi,min​(1−ai​)≤vi​≤vi,max​ai​
✅ Step 4: Constrain G_i based on a_i
Enforce:
Gi,min⁡ai+(1−ai)≤Gi≤−ai+Gi,max⁡(1−ai)G_{i,\min}a_i + (1 - a_i) ≤ G_i ≤ -a_i + G_{i,\max}(1 - a_i)Gi,min​ai​+(1−ai​)≤Gi​≤−ai​+Gi,max​(1−ai​)
Which guarantees:

• G_i < 0 if a_i = 1 (forward flux)
• G_i > 0 if a_i = 0 (reverse flux)

✅ Step 5: Final formulation as a MILP
Maximize: cᵀv
Subject to:

• Nv = 0 (steady state)
• Thermodynamic constraints:
  
  • For internal reactions:
    
    • Flux bounds with a_i
    • Gibbs energy bounds with a_i
  • P_int^TG = 0
• a_i ∈ {0,1}, G_i ∈ ℝ

Question 13

Part 3 | Essay question (10 pts)

Describe the key steps in generation of a genome scale metabolic model (3 points). Present the mathematical details of gap fill of your choice (7 points)

[ not the gap part - not covered in 24/25]

(2024_2,

Answer 13

1. Obtain genome annotation
   Genome position
   Coding region
   Locus name
   Gene function
   Protein classification (e.g. EC number)
2. Identify candidate metabolic functions
   Find genes encoding metabolic enzymes
3. Obtain candidate metabolic reactions for these functions
4. Assemble draft reconstruction
5. Collect experimental data for manual curration

Question 14

Part 5 - Extra credit question (10 points)
Mathematical program for shadow price derivative for metabolites in FBA (7 points). Discuss what these shadow prices provide regarding metabolite concentrations (3 points)

Answer 14

Mathematical program for shadow prices (7 pts)
We compute shadow prices (dual variables) as part of solving the dual of the FBA LP.

Let FBA be:
Primal LP (FBA):
max_v c^Tv
s.t. 
N·v = 0      (steady state)
v^min ≤ v ≤ v^max

The shadow prices correspond to dual variables μ of the equality constraint:
μ = ∂z^*/∂b, where b is the RHS of N·v = b (usually b = 0).

To compute μ, solve the dual LP:

Dual LP:
min_μ b^Tμ
s.t. 
N^Tμ ≤ c
(no inequalities for bounds here, assuming unbounded)

In FBA, this simplifies (with b = 0) to:
Find μ such that N^Tμ ≤ c

Interpretation of shadow prices (3 pts)

• Shadow prices μ_i correspond to metabolites (rows of N).
• Each μ_i represents the sensitivity of the objective (e.g. biomass) to a small change in the availability of metabolite i.
• If μ_i > 0: increasing metabolite i availability would increase the objective.
• If μ_i = 0: no impact on the objective.
• If μ_i < 0: increasing metabolite i would reduce the objective (rare in biomass FBA).

Question 15

Part 4 - Synthesis (15 points)

Given a set of reactions which can take the flux range between u1,u2 and l1,l2. And how to ensure that it increases the Biomass .

(2025_1)

Question 16

Part 5 - Extra credit question (10 points)

Formulation of Optstrain and explain the constraints, especially for the 3rd step of the optstrain approach

(2025_1)

Answer 16

3rd step of OptStrain focuses on identifying the minimum number of non-native reactions to add while maximizing target production.

key constraints ensure stoichiometric balance, limit flux ranges, activate/deactivate reactions using binary variables, restrict the number of added reactions, maintain minimum growth, and limit substrate uptake.

Question 17

Part 3 | Essay question (10 pts)

Flux Balance Analysis
Explain the basic assumptions and concepts of flux balance analysis, and make these precise in a mathematical form (5 pts). What are the underlying mathematical programming concepts? (5 pts)

(2018_test)

Answer 17

FBA based on assumption that organisms evolutionary optimize growth (cellular metabolism has evolved to maximize fitness)
so the objective is the maximation of biomass
optimize under steady state (gene expression and enzyme levels ~ constant over time) -> no change in metabolic concentrations
max cT x
s.t. Nv = 0
V_i^min <= v_i <= v_i^max
function must be convex in its segment

Question 18

Part 3 | Essay question (10 pts)

Flux Balance Analysis
Explain and provide examples of drawbacks to flux balance analysis. (2 pts) a (describe precisely the type of measurements needed, 3 pts). Total: 15 pts

(2018_test)

Answer 18

drawbacks: transient states require more involved approaches to be simulated
optimization of growth may not be the only objective -> bias in prediction

Question 19

Flux Coupling
Provide the definitions of the flux coupling types (5 pts).

(2018_test)

Answer 19

directional coupled: for Nv = 0, vi non zero implies vj non zero but not reverse
partial coupled: for Nv= 0, vi non zero implies vj non zero with vi/vj not constant and reverse full coupling: for Nv= 0, vi non zero implies vj non zero with vi/vj constant and reverse uncoupled else

Question 20

Flux Coupling
Provide the mathematical programs and appropriate transformations needed to solve the different types of coupling (5 pts).

(2018_test)

Answer 20

directional coupling: o <= vi/vj <= c OR c <= vi/vj
partial coupling: c1 <= vi/vj <= c2
full coupling: vi/vj = c
not coupled: 0 <= vi/vj
solve with linear fractional programm
transformed by charnes cooper transformation into linear
(2024_2, 2020_test, 2018_test)

Question 21

Flux Coupling
Illustrate each one of the flux coupling types on a small network (5 pts). Total: 15 pts

(2018_test)