Limits...
Partial inhibition and bilevel optimization in flux balance analysis.

Facchetti G, Altafini C - BMC Bioinformatics (2013)

Bottom Line: In order to keep the linearity and convexity of these nested optimization problems, an ON/OFF description of the effect of the perturbation (i.e. Boolean variable) is normally used.The more fine-graded representation of the perturbation allows to enlarge the repertoire of synergistic combination of drugs for tasks such as selective perturbation of cellular metabolism.This may encourage the use of the approach also for other cases in which a more realistic modeling is required.

View Article: PubMed Central - HTML - PubMed

Affiliation: SISSA (International School for Advanced Studies) Functional Analysis Dept, - Via Bonomea 265 - 34136, Trieste, Italy. altafini@sissa.it.

ABSTRACT

Motivation: Within Flux Balance Analysis, the investigation of complex subtasks, such as finding the optimal perturbation of the network or finding an optimal combination of drugs, often requires to set up a bilevel optimization problem. In order to keep the linearity and convexity of these nested optimization problems, an ON/OFF description of the effect of the perturbation (i.e. Boolean variable) is normally used. This restriction may not be realistic when one wants, for instance, to describe the partial inhibition of a reaction induced by a drug.

Results: In this paper we present a formulation of the bilevel optimization which overcomes the oversimplified ON/OFF modeling while preserving the linear nature of the problem. A case study is considered: the search of the best multi-drug treatment which modulates an objective reaction and has the minimal perturbation on the whole network. The drug inhibition is described and modulated through a convex combination of a fixed number of Boolean variables. The results obtained from the application of the algorithm to the core metabolism of E.coli highlight the possibility of finding a broader spectrum of drug combinations compared to a simple ON/OFF modeling.

Conclusions: The method we have presented is capable of treating partial inhibition inside a bilevel optimization, without loosing the linearity property, and with reasonable computational performances also on large metabolic networks. The more fine-graded representation of the perturbation allows to enlarge the repertoire of synergistic combination of drugs for tasks such as selective perturbation of cellular metabolism. This may encourage the use of the approach also for other cases in which a more realistic modeling is required.

Show MeSH

Related in: MedlinePlus

Convexity of L1- and L2-formulations and uniqueness of the solution. The two pictures report the unperturbed fluxes (vut) in the original set W. When the inhibition h is applied (dotted blue line), the set reduces to W(h). (a) With the L1-norm, balls are not strictly convex, therefore cases of multiple equivalent solutions may appear. As one can see, these situations occur only when the hyperplane of W(h) which realizes the minimum distance with respect to vut is parallel to an edge of the L1-ball. (b) Conversely, L2 balls are strictly convex and always lead to a unique solution.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4219332&req=5

Figure 2: Convexity of L1- and L2-formulations and uniqueness of the solution. The two pictures report the unperturbed fluxes (vut) in the original set W. When the inhibition h is applied (dotted blue line), the set reduces to W(h). (a) With the L1-norm, balls are not strictly convex, therefore cases of multiple equivalent solutions may appear. As one can see, these situations occur only when the hyperplane of W(h) which realizes the minimum distance with respect to vut is parallel to an edge of the L1-ball. (b) Conversely, L2 balls are strictly convex and always lead to a unique solution.

Mentions: Apart from the nonuniqueness of the unpertubed fluxes vut analyzed in the Additional file1, there are also other cases of degeneracy of the outcome of the algorithm, which we present here. Indeed, it is worth noting that the use of the norm L1 does not guarantee the uniqueness of the solution: indeed balls in L1 and the polytope W(h) are convex but not strictly convex sets. Unfortunately this limit can be overcome only passing to the L2 formulation with the consequent loss of the linearity of the problem. However, we expect that such a type of situations are quite rare since they appear only when the hyperplane (or the intersection of some of them) which defines W(h) and which realizes the minimum distance with respect to the vector vut, is parallel to an edge (or face) of the L1-ball (see Figure2).


Partial inhibition and bilevel optimization in flux balance analysis.

Facchetti G, Altafini C - BMC Bioinformatics (2013)

Convexity of L1- and L2-formulations and uniqueness of the solution. The two pictures report the unperturbed fluxes (vut) in the original set W. When the inhibition h is applied (dotted blue line), the set reduces to W(h). (a) With the L1-norm, balls are not strictly convex, therefore cases of multiple equivalent solutions may appear. As one can see, these situations occur only when the hyperplane of W(h) which realizes the minimum distance with respect to vut is parallel to an edge of the L1-ball. (b) Conversely, L2 balls are strictly convex and always lead to a unique solution.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4219332&req=5

Figure 2: Convexity of L1- and L2-formulations and uniqueness of the solution. The two pictures report the unperturbed fluxes (vut) in the original set W. When the inhibition h is applied (dotted blue line), the set reduces to W(h). (a) With the L1-norm, balls are not strictly convex, therefore cases of multiple equivalent solutions may appear. As one can see, these situations occur only when the hyperplane of W(h) which realizes the minimum distance with respect to vut is parallel to an edge of the L1-ball. (b) Conversely, L2 balls are strictly convex and always lead to a unique solution.
Mentions: Apart from the nonuniqueness of the unpertubed fluxes vut analyzed in the Additional file1, there are also other cases of degeneracy of the outcome of the algorithm, which we present here. Indeed, it is worth noting that the use of the norm L1 does not guarantee the uniqueness of the solution: indeed balls in L1 and the polytope W(h) are convex but not strictly convex sets. Unfortunately this limit can be overcome only passing to the L2 formulation with the consequent loss of the linearity of the problem. However, we expect that such a type of situations are quite rare since they appear only when the hyperplane (or the intersection of some of them) which defines W(h) and which realizes the minimum distance with respect to the vector vut, is parallel to an edge (or face) of the L1-ball (see Figure2).

Bottom Line: In order to keep the linearity and convexity of these nested optimization problems, an ON/OFF description of the effect of the perturbation (i.e. Boolean variable) is normally used.The more fine-graded representation of the perturbation allows to enlarge the repertoire of synergistic combination of drugs for tasks such as selective perturbation of cellular metabolism.This may encourage the use of the approach also for other cases in which a more realistic modeling is required.

View Article: PubMed Central - HTML - PubMed

Affiliation: SISSA (International School for Advanced Studies) Functional Analysis Dept, - Via Bonomea 265 - 34136, Trieste, Italy. altafini@sissa.it.

ABSTRACT

Motivation: Within Flux Balance Analysis, the investigation of complex subtasks, such as finding the optimal perturbation of the network or finding an optimal combination of drugs, often requires to set up a bilevel optimization problem. In order to keep the linearity and convexity of these nested optimization problems, an ON/OFF description of the effect of the perturbation (i.e. Boolean variable) is normally used. This restriction may not be realistic when one wants, for instance, to describe the partial inhibition of a reaction induced by a drug.

Results: In this paper we present a formulation of the bilevel optimization which overcomes the oversimplified ON/OFF modeling while preserving the linear nature of the problem. A case study is considered: the search of the best multi-drug treatment which modulates an objective reaction and has the minimal perturbation on the whole network. The drug inhibition is described and modulated through a convex combination of a fixed number of Boolean variables. The results obtained from the application of the algorithm to the core metabolism of E.coli highlight the possibility of finding a broader spectrum of drug combinations compared to a simple ON/OFF modeling.

Conclusions: The method we have presented is capable of treating partial inhibition inside a bilevel optimization, without loosing the linearity property, and with reasonable computational performances also on large metabolic networks. The more fine-graded representation of the perturbation allows to enlarge the repertoire of synergistic combination of drugs for tasks such as selective perturbation of cellular metabolism. This may encourage the use of the approach also for other cases in which a more realistic modeling is required.

Show MeSH
Related in: MedlinePlus