Project: Parallelization of Elementary Flux Mode enumeration for large-scale metabolic networks

Team: Fahad Khalid (Hasso-Plattner-Institute), Dr. Zoran Nikoloski (Max Planck Institute of Molecular Plant Physiology), Prof. Andreas Polze (Hasso-Plattner-Institute)

Research institution: Hasso Plattner Insitute and Max-Planck-Institute of Molecular Plant Physiology


This project aims at utilizing many-core, as well as GPU-based hardware architectures available in the FutureSOC Lab to develop a parallel high- performance solution for the aforementioned EFM problem. Parallel solutions to the problem under consideration have been only sparsely explored so far, which underlines the possibility of finding novel solutions in the area of parallel EFM algorithms by conducting the intended FutureSOC lab experiments.

An Elementary Flux Modes (EFM) is a set of minimal pathways in the metabolic network of an organism. Under steady-state conditions, the problem of finding EFMs in a metabolic network is mathematically equivalent to the enumeration of extreme rays of a polyhedral cone. This problem is computationally challenging, and the existing algorithms are incapable of enumerating EFMs for large-scale networks.

Research Highlights:

Following are the two fundamental areas of research in this project:

Computational Biology: Algorithmic enhancements for improving the efficiency of the enumeration process. One of the methods to achieve this is by introducing additional constraints to the solution space.

High Performance Computing: Improved strategies for utilizing heterogeneous parallel architectures. The focus is primarily on the EFM enumeration problem, however, further research in being conducted in applying the results to other combinatorial problems.

Project Description:

The metabolism is a collection of chemical reactions responsible for supporting life inside a living organism. They include reactions that breakdown organic matter in order to harvest energy; as well as those that utilize energy to construct the required chemicals e.g. proteins and nucleic acids. The processing of all these chemicals is carried out by the cell using a network of pathways.

The following image shows the metabolic network of the Arabidopsis thaliana citric acid cycle. Enzymes and metabolites are shown as red squares and the interactions between them as black lines.

The following image shows the first six reactions in the Glycolysis metabolic pathway. (Thomas Forth, 2010.)

Pathway analysis helps understand how an organism or parasite functions inside of the host cell. The resulting mathematical models serve as important step towards the full understanding of the complicated mechanisms around diseases. The results of such analysis efforts can contribute to drug engineering and better prevention approaches.

Elementary Flux Modes are computed using a sophisticated algorithm that starts with a matrix representation of the metabolic network under consideration. This matrix forms a system of homogenous linear equations. Thermodynamic constraints must be applied to the solutions space, which results in a convex polyhedral cone.

The following image shows a pointed polyhedral cone. One of the extreme rays is highlighted in red.

Last modified 9 years ago Last modified on Nov 12, 2012 3:31:18 PM

Attachments (3)

Download all attachments as: .zip