TreeEFM: calculating elementary flux modes using linear optimization in a tree-based algorithm.
BACKGROUND
Elementary flux modes (EFMs) analysis constitutes a fundamental tool in systems biology. However, the efficient calculation of EFMs in genome-scale metabolic networks (GSMNs) is still a challenge. We present a novel algorithm that uses a linear programming-based tree search and efficiently enumerates a subset of EFMs in GSMNs.


RESULTS
Our approach is compared with the EFMEvolver approach, demonstrating a significant improvement in computation time. We also validate the usefulness of our new approach by studying the acetate overflow metabolism in the Escherichia coli bacteria. To do so, we computed 1 million EFMs for each energetic amino acid and then analysed the relevance of each energetic amino acid based on gene/protein expression data and the obtained EFMs. We found good agreement between previous experiments and the conclusions reached using EFMs. Finally, we also analysed the performance of our approach when applied to large GSMNs.


METHODS
The stand-alone software TreeEFM is implemented in C++ and interacts with the open-source linear solver COIN-OR Linear program Solver (CLP).
CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK.
Jon
J
Pey
CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK.
Juan A
JA
Villar
CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK.
Luis
L
Tobalina
CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK.
Alberto
A
Rezola
CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK.
José Manuel
JM
García
CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK.
John E
JE
Beasley
CEIT and TECNUN, University of Navarra, Manuel de Lardizabal 15, 20018 San Sebastian, Spain, Computer Engineering Department, School of Computer Science, POB 30100 University of Murcia, Spain and Mathematical Sciences, Brunel University, Kingston Lane, UB8 3PH Uxbridge, UK.
Francisco J
FJ
Planes
D000085:Acetates / Q000378:metabolism*; D000465:Algorithms; D000596:Amino Acids / Q000378:metabolism; D004926:Escherichia coli / Q000378:metabolism*; D020869:Gene Expression Profiling; D016680:Genome, Bacterial; D064688:Metabolic Flux Analysis / Q000379:methods*; D053858:Metabolic Networks and Pathways; D011382:Programming, Linear; D012984:Software
D000085:Acetates; D000596:Amino Acids