Metabolic Networks, Thermodynamic Constraints, and Matroid Theory

Abstract

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.

Biologische Experimente sind zeitraubend und teuer. Deshalb werden Computer immer häufiger benutzt um solche Experimente zu bestimmen, die am ehesten erfolgreich sind und zu neuen Erkenntnissen führen. In dieser Arbeit betrachte ich Varianten der Constraint-Basierten Methode Flussbalance-Analyse. Mittels Nebenbedingungen werden biologisch unrealistische Verhaltensweisen ausgeschlossen. Viele der Nebenbedingungen (z.B. Flusserhaltung) lassen sich mit linearen Ungleichungen beschreiben, was effiziente Analyse mittels linearer Programmierung ermöglicht. Thermodynamische Nebenbedingungen sorgen dafür, dass auch energetische Aspekte berücksichtigt werden. Allerdings sind diese Nebenbedingung nicht linear und induzieren zudem oft einen nicht abgeschlossenen Lösungsraum. In dieser Arbeit zeige ich, dass diese nicht- Linearität der thermodynamischen Nebenbedingungen häufig zu NP-schweren Problemen führt, was sich z.B. auf die Verlässlichkeit von Samplingmethoden auswirkt. Aber ich diskutiere auch Lösungsansätze, wie dennoch in der Praxis Optimierungsprobleme und qualitative Analysemethoden, wie Flusskopplungsanalse, mit thermodynamischen Nebenbedingungen effizient gelöst werden können. Anwendung finden diese Erkenntnisse in der Analyse des Wachstum der Grünalge C. reinhardtii, wo ich eine Methode zum Lösen von bilevel- Optimierungsproblemen mit thermodynamischen Nebenbedingungen entwickle. Ein weiteres Gebiet meiner Arbeit umfassen Flussmodule. Inspiriert von einer Arbeit von Kelk et al. gebe ich eine mathematische Definition von Flussmodul und zeige dass die Definition die erwünschten Eigenschaften erfüllt. Die Definition erlaubt mir auch mehrere Zerlegungsätze zu zeigen, die die Analyse metabolischer Netzwerke vereinfachen, und Module effizient mittels Matroidtheorie zu finden. Mit der Definition von k-Modul zeige ich auch einen Zerlegungssatz für die Eckenenumeration allgemeiner Polyeder und nutze hierfür das Konzept der Branchweite in Matroiden. Mittels Flussmodulen und algorithmischen Ansätzen um auch komplizierte Nebenbedingungen zu integrieren, zeige ich in dieser Arbeit Methoden auf, die die Analyse metabolischer Netzwerke vereinfachen und beschleunigen. Dadurch können biologische Erkenntnisse schneller gewonnen werden und bessere Methoden in der Biotechnologie zur Herstellung von Biotreibstoffen und in der Medizin für Krebstherapien entwickelt werden.