Hintergrund

Die elementare Flussmodenanalyse (EFMA) ist eine sehr leistungsfähige Methode zur Untersuchung von metabolischen Netzwerken in einem Gleichgewichtszustand. Sie basiert auf dem Konzept der elementaren Flussmodi (EFMs), bei denen es sich um minimale Funktionseinheiten eines metabolischen Netzwerks handelt. Das Aufzählen von EFMs ist sehr ressourcenintensiv und erfordert sehr viel Speicher. Derzeit können EFMs nur für kleine und mittlere Modelle berechnet werden.

Methoden

In dieser Arbeit werden zwei Ansätze zur vollständigen Nummerierung von EFMs miteinander verglichen. Einer dieser Ansätze - die „double description“ Methode (DDM) ist unter Systembiologen sehr verbreitet. Efmtool wurde als Repräsentant für die DDM ausgewählt, da es eine der beliebtesten Implementierungen der DDM ist. Es verfügt über einen parallelen Modus, der auf einzelnen Servern ausgeführt werden kann, und gilt als eines der schnellsten und besten Tools zur Berechnung von EFMs. Der andere Ansatz basiert auf dem „lexicographic reverse search“ (lrs) Algorithmus. Dieser Algorithmus wurde für die Aufzählung der Scheitelpunkte und extremen Strahlen von Polyedern entwickelt. Obwohl das zugrunde liegende Problem der Berechnung von EFMs und der Aufzählung der Scheitelpunkte und extremen Strahlen von Polyedern mathematisch äquivalent ist, wird der lrs Algorithmus aufgrund extrem langer Laufzeiten als nicht geeignet für die Nummerierung von EFMs angesehen. Die neuen parallelen Implementierungen (plrs und mplrs) des lrs Algorithmus scheinen jedoch vielversprechend zu sein, da sie die Laufzeit erheblich reduzieren, wenn sie auf mehreren Servern in einem Cluster ausgeführt werden, wie dies in unabhängigen Fällen gezeigt wird.

Ergebnisse

Hier zeigen wir, dass (mp) lrs ähnliche Laufzeiten erreicht, wenn er in mittelgroßen Clustern ausgeführt wird und das Netzwerk zuvor stark komprimiert wurde. Außerdem zeigt der mplrs Algorithmus ein nahezu ideales Skalierungsverhalten und hat nicht den umfangreichen Speicherbedarf, den efmtool benötigt.

Fazit

Unsere Ergebnisse bestätigen, dass der mplrs eine attraktive Alternative zum efmtool ist. Der mplrs zeigt ein beinahe ideales Skalierungsverhalten bei geringem Speicherbedarf. Es scheint, dass die Berechnung von EFMs in metabolischen Netzwerken im „genom-weiten“ Maßstab in Reichweite kommt, wenn der mplrs auf der derzeit verfügbaren Infrastruktur für Hochleistungscomputer ausgeführt wird.

Background

Elementary flux mode analysis (EFMA) is a very powerful method for studying metabolic networks under steady-state conditions. It is based on the concept of elementary flux modes (EFMs) which are minimal functional units of a metabolic network. Enumerating EFMs are very resource demanding computations that require a huge amount of memory. Currently it is only possible to calculate EFMs for small and medium sized models.

Methods

In this thesis two approaches for the complete enumeration of EFMs are being compared against each another. One of these approaches - the double description method (DDM) is very common among system biologists. Efmtool was chosen to represent the double description method as it is one of its most popular implementations. It has a parallel mode that is executable on single servers and is believed to be one of the fastest and best tools available for calculating EFMs. The other is a based on the lexicographic reverse search (lrs) algorithm. This algorithm was developed for the enumeration of the vertices and extreme rays of polyhedra. Although the underlying problem of calculating EFMs and enumerating the vertices and extreme rays of polyhedra is mathematically equivalent, the lrs algorithm is regarded to be not suitable for calculating EFMs due to extremely long runtimes. However, the new parallel implementations (plrs and mplrs) of the lrs algorithm seem very promising as they significantly reduce the runtime when executed on several servers in a cluster as shown in unrelated cases.

Results

Here, we show that (mp)lrs achieves similar runtimes if executed on medium sized clusters and if the network has been extensively compressed before. Moreover, mplrs shows an almost ideal scaling behavior and does not impose the extensive memory demands required by efmtool.

Conclusions

Our results confirm that mplrs is an attractive alternative to the efmtool. mplrs shows ideal scaling behavior and low memory demand. Thus, it appears that the enumeration of EFMs in genome-scale metabolic models will come within reach, if mplrs is executed on currently available high-performance computing infrastructure.