Thursday, 13:45 - 14:10 h, Room: H 2013


Arne Müller
Cycle free flows in large-scale metabolic networks


Genome-scale metabolic networks are used to model all (usually around 2000) chemical reactions occuring in a biological cell. These networks are a generalization of directed hypergraphs (where the reactions are the arcs of the graph) and a specialization of realizable oriented matroids.
We are interested in optimizing the flow through a given reaction in the network. We have the usual constraint of flow conservation and additionally the flow must not contain internal circuits. Internal circuits are flows that do not contain a specific subset of the reactions called exchange reactions.
We show that it is NP-hard to decide if a non-zero flow without internal circuits through a given reaction is possible. However, most genome-scale metabolic networks only contain few internal circuits. Using a specific branching strategy combined with a primal heuristic, we derive a tractability result that is also practically applicable. In fact, it very often suffices to solve only one LP.
For flux variability analysis, where we solve optimization problems for each reaction in the network, we obtain a speed-up of factor 30-300 to previous methods.


Talk 2 of the contributed session Thu.2.H 2013
"Network analysis" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  The deal is that Indiana Payday Loans online can save your time, nerves and make a solution of all your financial problems. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Buy Cialis is the one that definitely differs from all other products.