Arne C. Reimers:
Metabolic Networks, Thermodynamic Constraints, and Matroid Theory
Biological experiments are time-consuming and expensive. Hence, computer-aided experimental design is used more and more often to select those experiments that are likely to yield new insights. In this work I consider variants of the constraint based method Flux Balance Analysis. Constraints are used to exclude biologically unrealistic phenotypes. Many constraints (for example flow conservation) can be formulated using linear inequalities, which allows efficient analysis using linear programming. Thermodynamic constraints are used to include also energetic aspects. However, thermodynamic constraints are not linear and induce a non-closed solution space. In this work I show that this non-linearity of thermodynamic constraints often leads to NP-hard decision problems. I show how this has consequences on the reliability of sampling methods. However, I also present solution approaches that allow us to solve optimization problems and qualitative analysis methods, like flux coupling analysis with thermodynamic constraints efficiently in practice. These insights I then use to develop a bi-level optimization method to analyze a growth behavior of the green alga Chlamydomonas reinhardtii. Another area covered by this work are flux modules. Based on a work by Kelk et al., I give a mathematical definition of flux module and show that this definition satisfies the desired properties. This definition also allows me to show several decomposition theorems. These decomposition theorems simplify the analysis of metabolic networks. Using matroid theory I show how modules can efficiently be computed. With the definition of k-module, I also show a decomposition theorem for general polyhedra using the concept of matroid branch-width. With flux modules and algorithmic approaches to also include complex constraints I present methods in this thesis that simplify and speed- up the analysis of metabolic networks. This allows us to gain biological insights faster and develop better methods for the production of bio-fuels in bio-engineering and cancer therapies in medicine.