TY - GEN

T1 - Parallel out-of-core algorithm for genome-scale enumeration of metabolic systemic pathways

AU - Samatova, N. F.

AU - Geist, A.

AU - Ostrouchov, G.

AU - Melechko, A.

N1 - Publisher Copyright:
© 2002 IEEE.

PY - 2002

Y1 - 2002

N2 - Systemic pathways-oriented approaches to analysis of metabolic networks are effective for small networks but are computationally infeasible for genome scale networks. Current computational approaches to this analysis are based on the mathematical principles of convex analysis. The enumeration of a complete set of "systemically independent" metabolic pathways is at the core of these approaches and it is computationally the most demanding component. An efficient parallel out-of-core algorithm for generating a complete set of systemically independent metabolic pathways, termed "extreme pathways", is presented. These pathways represent the edges of a high-dimensional convex cone and can be used to derive any admissible steady-state flux distribution (or phenotype) for a specified metabolic genotype. The algorithm can be used for computing "elementary flux modes" that are different but closely related to extreme pathways. The algorithm combines a bitmap data representation, search space reduction, and out-of-core implementation to improve CPU-time and memory requirements by several orders of magnitude. Augmented with a parallel implementation, it provides extremely scalable performance. No previous parallel and/or out-of-core algorithms for the enumeration of systemically defined metabolic pathways are known.

AB - Systemic pathways-oriented approaches to analysis of metabolic networks are effective for small networks but are computationally infeasible for genome scale networks. Current computational approaches to this analysis are based on the mathematical principles of convex analysis. The enumeration of a complete set of "systemically independent" metabolic pathways is at the core of these approaches and it is computationally the most demanding component. An efficient parallel out-of-core algorithm for generating a complete set of systemically independent metabolic pathways, termed "extreme pathways", is presented. These pathways represent the edges of a high-dimensional convex cone and can be used to derive any admissible steady-state flux distribution (or phenotype) for a specified metabolic genotype. The algorithm can be used for computing "elementary flux modes" that are different but closely related to extreme pathways. The algorithm combines a bitmap data representation, search space reduction, and out-of-core implementation to improve CPU-time and memory requirements by several orders of magnitude. Augmented with a parallel implementation, it provides extremely scalable performance. No previous parallel and/or out-of-core algorithms for the enumeration of systemically defined metabolic pathways are known.

UR - http://www.scopus.com/inward/record.url?scp=84966586597&partnerID=8YFLogxK

U2 - 10.1109/IPDPS.2002.1016588

DO - 10.1109/IPDPS.2002.1016588

M3 - Conference contribution

AN - SCOPUS:84966586597

T3 - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002

SP - 185

EP - 192

BT - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 16th International Parallel and Distributed Processing Symposium, IPDPS 2002

Y2 - 15 April 2002 through 19 April 2002

ER -