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

**Arne MÃ¼ller**

Cycle free flows in large-scale metabolic networks

**Abstract:**

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"** [...]