Exam Questions Flashcards

Question

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 1

Mathematical Program for Minimizing Total Flux Sum (8 points) Minimize the total absolute flux sum: min∑𝑖∣𝑣_𝑖∣∣ Constraints: Steady-State Mass Balance: 𝑆𝑣 =0 where: 𝑆 is the stoichiometric matrix (𝑚×𝑛), 𝑣 is the flux vector (𝑛-dimensional). Flux Bounds: 𝑣_𝑖^𝑚𝑖𝑛 ≤ 𝑣_𝑖 ≤ 𝑣_{𝑖^𝑚𝑎𝑥

Biomass Constraint (if applicable):
𝑣_biomass ≥ 𝑓^∗

Linearization of Absolute Values: v_i⁺ and
v_i⁻ such that:
v_i=v_i⁺−v_i⁻,v_i⁺,v_i⁻≥0

Objective function becomes:

min i∑ (v_i⁺+v_i⁻)

Illustration on a Small Example Network (2 points)

Consider a simple metabolic network with three reactions:
A→B (Flux: v₁)
B→C (Flux: v₂)
C→D (Flux: v₃)

Stoichiometric matrix S:
𝑆 =
[−1 0 0
1 −1 0
0 1 −1
0 0 1]

Solving the pFBA problem ensures minimal total flux while maintaining steady-state constraints, leading to an efficient flux distribution.}

Answer 2

from google doc 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 ROOM: regulary changes in genetic, gene knock outs are minimized MILP flux has to show significant change bounds based on bounds of wild type and relative changes and sensitivity bound improves correlation of fluxes compared to MOMA MOMA and ROOM Explain how robustness analysis of the predictions can be carried out (5 pts). Partial knock-outs by modifying upper bounds -> recalculating optimum for the mutant and the MOMA projection Sampling-based: sample around the FBA optimum -> determine MOMA projections, allows to study alternative optima to MOMA -------------- perplexity: MOMA vs. ROOM MOMA (Minimization of Metabolic Adjustment) Assumes: Fluxes adjust smoothly after a gene knockout Objective: Minimize Euclidean distance from wild-type flux Equation: min∑(v_mut,i−v_wt,i) ² Pseudocode: minimize || v_mut - v_wt ||² subject to: S * v_mut = 0 v_lb ≤ v_mut ≤ v_ub Computational Complexity: Polynomial-time Lecture Context: Quadratic programming, gene knockouts ROOM (Regulatory On/Off Minimization) Assumes: Minimal flux changes after a gene knockout Objective: Minimize number of flux changes Equation: min min∑δ_i δ_i = 1 if |v_mut,i - v_wt,i| > ε, else 0 Pseudocode: minimize ∑ δ_i subject to: S * v_mut = 0 v_lb ≤ v_mut ≤ v_ub δ_i = 1 if |v_mut,i - v_wt,i| > ε else 0 Computational Complexity: NP-hard Lecture Context: Sparse optimization, integer programming Key Differences MOMA - Quadratic programming, minimizes flux deviation ROOM - MILP, minimizes number of flux changes MOMA - Easier (polynomial), assumes smooth adaptation ROOM - Harder (NP-hard), assumes regulatory constraints limit changes Now exactly how you wanted.

Answer 3

Charnes-Cooper Transformation in FCA and Its Application (10 points) 1. Definition of Charnes-Cooper Transformation The Charnes-Cooper transformation is used to convert linear fractional programs (LFPs) into linear programs (LPs), making them easier to solve. A linear fractional program (LFP) has the form: min e Tx+fc T x+d subject to: Ax≤b,x≥0 where c,e,A,b are given vectors/matrices. To transform it into a linear program (LP), define a new variable: t= e T x+f 1 and substitute y=xt, giving a new LP: ⁡ mincTy+dt subject to: Ay≤bt,e T y+ft=1,y≥0,t≥0 2. Application in Flux Coupling Analysis (FCA) Flux Coupling Analysis (FCA) identifies dependencies between reaction fluxes. In full coupling, two fluxes v_i and v_j maintain a constant ratio: v_jv_i =c for some constant 𝑐 Since this is a fractional constraint, it can be transformed using Charnes-Cooper, defining: t= v_j 1 Rewriting: v_i=cv_j⇒v_it=c This allows solving linear constraints rather than fractional constraints. 3. Practical Use in Metabolic Networks Used in FCA to check reaction coupling by converting fractional dependencies into LP constraints. Helps detect fully, partially, or directionally coupled reactions in metabolic networks. Makes bi-level optimization problems solvable in FBA extensions like OptKnock and OptStrain. This transformation is crucial for simplifying non-linear metabolic constraints into LP problems for efficient computational solving.

Answer 4

**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.

Answer 5

google doc: (pFBA + MinMax + TMFA??!!). --- perplexity chat Part 4 - Synthesis (15 points) Metabolite M_i Flux Ranges (pFBA + MinMax + TMFA) Base constraints: Mass balance: S⋅v = 0 (stoichiometric matrix S, flux vector v). Flux bounds: α_j ≤ v_j ≤ β_j (physiological limits). pFBA: Minimize Σv_j² (parsimonious flux) + optimal growth. Thermodynamic (TMFA) constraints: Reaction directionality: v_j⋅Δ_rG_j' ≤ 0 (flux aligns with ΔG). Metabolite activity: Δ_rG_j' = Δ_rG_j'° + RT⋅ln(Πa_i^ν_ij) (a_i = activity of M_i). Extended steps for M_i: Identify all reactions with M_i in S. Apply TMFA: Enforce Δ_rG_j' ≤ 0 if v_j > 0 (linearize ln(a_i)). Re-run MinMax to get [v_j,min, v_j,max] under thermodynamic limits. Key outcomes: Eliminate infeasible loops (e.g., futile cycles). Tighter flux bounds due to metabolite activity constraints. Reversible ↔ irreversible reactions clarified via Δ_rG_j'. Exam focus: Integrate pFBA (optimal flux), MinMax (variability), and TMFA (thermo feasibility) for realistic flux ranges.

Answer 6

(Answer said by Anika (not Zoran) was OptStrain, but please double check it as I am not sure.)

Answer 7

stevie thinks: only positive stoichiometric coefficients

Answer 8

stevie thinks: correlatkion 1

Answer 9

The function 𝑥^𝑇𝑄𝑥 is a quadratic form, and its concavity depends on the properties of the matrix 𝑄 Concave function: A function is concave if its Hessian (in this case, the matrix 𝑄) is negative semidefinite. Convex function: A function is convex if 𝑄 is positive semidefinite. Evaluating the Options for Concavity (a) Indefinite ❌ Incorrect – An indefinite matrix has both positive and negative eigenvalues, meaning the function is neither concave nor convex. (b) Positive semidefinite (for convex) ❌ Incorrect – A positive semidefinite matrix leads to a convex function, not concave. (c) Positive definite (for strictly convex) ❌ Incorrect – A positive definite matrix ensures strict convexity, not concavity. (d) Negative semidefinite ✅ Correct – If 𝑄 is negative semidefinite, then 𝑥^𝑇𝑄𝑥 is concave. Final Answer: (d) Negative semidefinite

Answer 10

False. Shadow prices in a canonical linear program (LP) correspond to the change in the objective function resulting from a marginal change in the right-hand side (RHS) of a constraint, not the upper bound of the constraint. If the LP is in standard form: max ⁡ 𝑐 𝑇 𝑥 maxc T x subject to: 𝐴 𝑥 ≤ 𝑏 , 𝑥 ≥ 0 Ax≤b,x≥0 The shadow price of a constraint measures how much the optimal objective value changes per unit increase in the RHS value 𝑏 𝑖 b i . It is given by the dual variables (Lagrange multipliers) in the dual LP. Changes in upper bounds (e.g., variable limits) do not directly correspond to shadow prices but rather to reduced costs or sensitivity analysis of variable bounds.

Answer 11

1. LP of OptReg and Interval Obtainment OptReg (Optimal Regulation) LP Formulation: Converts a linear fractional problem (LFP) to a standard LP using auxiliary variables. For an LFP: maximize c T x d T x subject to A x ≤ b , x > 0 maximize d T x c T x subject to Ax≤b,x>0 It is transformed into an LP: maximize c T x ′ subject to A x ′ ≤ t b , d T x ′ = 1 , t ≥ 0 maximize c T x ′ subject to Ax ′ ≤tb,d T x ′ =1,t≥0 where x ′ = x d T x x ′ = d T x x and t = 1 d T x t= d T x 1 . Interval Obtainment: Use interval coefficients in LP to handle uncertainty (e.g., reaction flux bounds). For interval LP: maximize c T x with A − x ≤ b + , x ≥ 0 maximize c T x with A − x≤b + ,x≥0 Solve for upper/lower bounds via worst-case optimization (e.g., c T x c T x under A − A − and A + A + constraints).

Answer 12

2. SBC Definition and Constraint-Based Steady-State Flux SBC (Simulation-Based Calibration): Validates model/algorithm consistency by simulating datasets from priors, fitting the model, and checking if posterior ranks are uniform. Failure indicates mismatched model, data generator, or algorithm. Constraint-Based Approach Without SBC: Use flux balance analysis (FBA) with: Stoichiometric matrix: S ⋅ v = 0 S⋅v=0 (mass balance). Flux bounds: α j ≤ v j ≤ β j α j ≤v j ≤β j (physiological limits). LP optimization: Maximize biomass (e.g., maximize v biomass maximize v biomass ). Excludes SBC’s posterior checks; relies solely on stoichiometric and thermodynamic constraints.

Answer 13

3. Genome-Scale Metabolic Model Steps and Gap Filling Key Steps: Gene annotation: Identify metabolic genes (e.g., via BLAST). Reaction inclusion: Map genes to enzymes/reactions (e.g., KEGG). Stoichiometric matrix: Compile reactions into S S (rows = metabolites, columns = reactions). Test growth: Simulate under media conditions; iteratively add/remove reactions for biological plausibility. Gap-Filling LP Formulation: Minimize added reactions to enable growth: minimize ∑ ∣ y j ∣ minimize ∑∣y j ∣ subject to: S ⋅ v + y = 0 S⋅v+y=0 v biomass ≥ v min v biomass ≥v min α j ≤ v j ≤ β j α j ≤v j ≤β j where y j y j represents gap-filled reactions.

Answer 14

Part 4: Mathematical Program for Nv = 0 with Biomass Optimization and Total Metabolite Flux Input Variables: v j + , v j − ≥ 0 v j + ,v j − ≥0 (split fluxes into positive/negative components). Objective: Maximize c biomass ⋅ ( v biomass + − v biomass − ) Maximize c biomass ⋅(v biomass + −v biomass − ) Constraints: Mass balance: N ( v + − v − ) = 0 N(v + −v − )=0. Total flux per metabolite: ∑ j ∈ J i ( v j + + v j − ) = T i ∑ j∈J i (v j + +v j − )=T i (for each metabolite i i, given input T i T i ). Flux bounds: v j + ≤ U j v j + ≤U j , v j − ≤ − L j v j − ≤−L j . Assumption: The system optimizes biomass yield (objective function).

Answer 15

Part 5: Shadow Price Derivatives in FBA Mathematical Program: Solve the dual LP of the FBA primal problem: Primal: Max c T v s.t. N v = 0 , L ≤ v ≤ U . Max c T vs.t. Nv=0,L≤v≤U. Dual Variables: λ i λ i : Shadow price for metabolite i i (dual of N v = 0 Nv=0). μ j , ν j μ j ,ν j : Duals for flux bounds L ≤ v ≤ U L≤v≤U. Shadow Price Derivative: λ i = ∂ ( biomass ) ∂ b i λ i = ∂b i ∂(biomass) , where b i b i is a perturbation in metabolite i i’s mass balance. Interpretation for Concentrations: High λ i λ i : Metabolite i i is growth-limiting; increasing its concentration boosts biomass. Low λ i λ i : Metabolite i i is non-critical or abundant. Exam Focus: Shadow prices quantify metabolite criticality and guide concentration adjustments for optimal growth.

Answer 16

Part 4 - Synthesis (15 points) To increase biomass while considering flux ranges for reactions: Flux Constraints: For each reaction j: l 1 j ≤ v j − ≤ l 2 j l 1j ≤v j − ≤l 2j u 1 j ≤ v j + ≤ u 2 j u 1j ≤v j + ≤u 2j v j = v j + − v j − v j =v j + −v j − Biomass Optimization: Maximize v biomass Maximize v biomass Mass Balance Constraint: S ⋅ v = 0 S⋅v=0 Total Flux Constraint (if applicable): ∑ j ∈ J i ( v j + + v j − ) = T i ∑ j∈J i (v j + +v j − )=T i Irreversibility Constraints: For irreversible reactions: v j − = 0 v j − =0 To ensure increased biomass: Adjust upper bounds (u_1j, u_2j) for reactions contributing to biomass production. Tighten lower bounds (l_1j, l_2j) for competing reactions. Iterate optimization, adjusting bounds based on shadow prices to identify flux-limiting reactions.

Answer 17

Part 5 - Extra credit question (10 points) OptStrain Formulation (focusing on the 3rd step): Objective Function: Maximize v target − y ⋅ v biomass Maximize v target −y⋅v biomass Where v_target is the flux of the target metabolite and y is a small positive number. Constraints: a) Stoichiometric balance: S ⋅ v = 0 S⋅v=0 b) Flux bounds: v j min ≤ v j ≤ v j max v j min ≤v j ≤v j max c) Reaction activation: v j min ⋅ y j ≤ v j ≤ v j max ⋅ y j v j min ⋅y j ≤v j ≤v j max ⋅y j Where y_j is a binary variable (0 or 1) indicating if reaction j is active. d) Maximum number of added reactions: ∑ j ∈ J added y j ≤ N max ∑ j∈J added y j ≤N max Where J_added is the set of added reactions and N_max is the maximum allowed. e) Minimum biomass production: v biomass ≥ v biomass min v biomass ≥v biomass min f) Maximum substrate uptake: v substrate ≤ v substrate max v substrate ≤v substrate max The 3rd step of OptStrain focuses on identifying the minimum number of non-native reactions to add while maximizing target production. The 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.

Answer 18

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

Answer 19

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

Answer 20

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

Answer 21

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)

Answer 22

if absolute value contains linear function, it can be reformulated into two linear expressions Z=|x| -> z = x for x>=0 and -z = x for x<=0

Answer 23

rewrite constraints and add additional binary variable leads to MILP

Brainscape's Knowledge GenomeTM

Exam Questions Flashcards

Brainscape's Knowledge Genome^TM