Algorithms for the constraint-based analysis of metabolic networks

Abstract

Constraint-based analysis of genome-scale metabolic networks has become increasingly important for describing and predicting the cellular behavior of living organisms. The steady-state constraints provide a reliable framework without the need for additional kinetic details of the system. As the number of metabolic network reconstructions and their level of detail continually increases, many computational tools for their analysis become unpractical to use. This invites for more efficient algorithms and tools for the analysis of metabolic networks. We have a two-fold aim with this work: first, to design new algorithms that improve the efficiency of some of the existing methods, secondly to create additional tools that fill in gaps in our toolbox for metabolic network analysis. These methods will provide additional insight into the structure of metabolic networks and ultimately broaden our understanding of cellular systems. In the first part of the thesis we focus on improving flux coupling analysis (FCA). We prove that solving certain linear programs to feasibilty is sufficient to correctly deduce most coupling information. The FFCA algorithm improves the efficiency of existing algorithms in the literature and is further developed by proving that all fully coupled reactions can be computed algebraically. Utilizing the transitive nature of couplings and reusing existing LP solutions we can dramatically decrease running-time. Using these improvements we design the F2C2 algorithm. We extend the concepts of FCA to the constrained flux space, where any number of additional linear constraints can be imposed on the reactions. Constrained flux coupling analysis (CFCA) is proven to reveal coupling information that is only visible under special environmental conditions. We study the relationship between the FCA and CFCA relations and present an efficient algorithm to compute the latter. In our next effort we study whether relations similar to FCA could also be applied for metabolites. We introduce the concept of metabolic activity coupling (MAC), which finds implicative relations between the momentary production and consumption of different metabolites. Elementary flux modes (EM) are a canonical representation of the steady-state flux space. Our novel method for finding EMs containing several predefined reactions can be used to identify pathways that synthesize a desired target from one or more source metabolites. While the problem solved belongs to the class of NP-hard problems, we show that for current-generation networks the method is applicable in practice. In the last part of the thesis, we show that the study of isolated subnetworks may result in undesired artifacts, and as an alternative solution, we present a method that projects the flux space onto lower dimension, while preserving key features of the network. We show that in certain cases our method can be applied where an exhaustive EM enumeration would otherwise fail.

Constraint-basierte Analyse von genomweiten metabolischen Netzwerken ist zunehmend immer wichtiger geworden, um das Zellverhalten von Lebenswesen zu beschreiben und vorherzusagen. Die sogenannten 'steady-state' Bedingungen bieten einen verlässlichen Rahmen, ohne zusätzliche kinetische Einzelheiten des Systems zu brauchen. Da die Anzahl des Wiederaufbaus des Stoffwechselnetzwerks und deren Detaillierungsgrad fortwährend steigt, sind viele Rechenmitteln für deren Analyse ungeeignet. Dies gibt Anlass für effizientere Algorithmen und Mitteln für die Analyse von metabolischen Netzwerken. Wir haben mit dieser Arbeit ein zweifaches Ziel: erstens, neue Algorithmen zu gestalten, die die Laufzeit von einigen bestehenden Verfahren verbessern und zweitens, zusätzliche Werkzeuge zu erstellen, die die Lücken in unserem Werkzeugkasten für Stoffwechselnetzwerkanalyse erfüllen. Diese Verfahren werden zusätzlichen Einblick in die Struktur des metabolischen Netzes geben und schließlich unser Verständnis der zellulären Systeme erweitern. Im ersten Teil der Arbeit konzentrieren wir uns darauf, die Flusskopplungsanalyse (FCA) zu verbessern. Wir beweisen, dass es ausreichend ist, bestimmte lineare Programme zur Ausführbarkeit zu lösen, um die meisten Verkopplungsinformationen richtig herzuleiten. FFCA ist effizienter als in der Literatur bestehenden Algorithmen und wird weiter entwickelt, weil alle vollständig gekoppelten Reaktionen algebraisch berechnet werden können. Durch die Anwendung der Transitivität der Koppelbeziehungen und die Wiederverwendung der bestehenden LP kann die Laufzeit sich drastisch vermindern. Wir erweitern die Vorstellungen der FCA auf die eingeschränkte flux space, in welchem eine beliebige Anzahl von zusätzlichen linearen Einschränkungen auf die Reaktionen zur Folge haben kann. Wir untersuchen die Beziehung zwischen den FCA und CFCA Beziehungen und stellen einen effizienten Algorithmus dar, um CFCA zu errechnen. Folgend, wir stellen das Konzept der Stoffwechselaktivität Kopplung (MAC) vor, das auswirkende Beziehungen zwischen der Herstellung und Verbrauch von verschiedenen Metaboliten findet. Elementare Flussmoden (EM) sind eine anerkannte Darstellung der 'steady-state' Flussraum. Unsere neue Methode, um EM-en, die mehrere vordefinierten Reaktionen beinhalten, kann verwendet werden, um Wege, die ein gewünschtes Ziel aus einem oder mehreren Quellmetaboliten zu synthetisieren, zu identifizieren. Wir zeigen, dass für die current-generation Netzwerke das Verfahren in der Praxis noch anwendbar ist. Die Analyse isolierten Teilnetze können zu unerwünschten Artefakten führen. Wir präsentieren eine Methode, in wecher der Flussraum auf eine untere Dimension so projektiert wird, dass die wichtigsten Features des Netzwerks beibehalten werden. Wir zeigen, dass in bestimmten Füllen solche Verfahren in Situationen eingesetzt werden können, wo eine erschöpfende EM Aufzählung sonst scheitern würde.