User:Jarle Pahr/OptKnock
Notes on the OptKnock algorithm:
OptKnock is a bi-level optimization algorithm that seeks to optimize metabolite production through gene knockouts, subject to maximization of the cellular objective.
Problem formulation:
- Direct solution intractable
- Solution approach based on LP duality theory. Basis: "For every linear programming problem (primal) there exists a unique optimization problem (dual) whose optimal objective value is equal to that of the primal problem." (Burgard 2003).
http://maranas.che.psu.edu/submission/optknock_2.htm
Flaw:
Xu et al (http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3859475/pdf/pone.0072150.pdf) point out a flaw in the justification of the transformation of the bi-level problemt o a MILP as performed by Burgard et al. They cite Scott DeNegre in INTERDICTION AND DISCRETE BILEVEL LINEAR PROGRAMMING (PhD thesis), who writes:
"In their model, Burgard et al. (2003) utilize binary upper-level variables to represent yes/no decisions regarding the gene knockouts and reformulate the the problem using lower-level duality. Rather than using KKT conditions, the y instead enforce lower-level primal and dual feasibility and require the primal and dual objectives to be equal. However, they neglect to include the lower-level primal variables in the dual object ive and, thus, erroneously state that a MILP formulation has been derived. "
Related methods
MOMA-Knock: http://www.biomedcentral.com/1471-2105/14/S2/S17
ReacKnock: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3859475/pdf/pone.0072150.pdf
