Parallelization of Nullspace Algorithm for the computation of metabolic pathways

Dimitrije Jevremović; Cong T. Trinh; Friedrich Srienc; Carlos P. Sosa; Daniel L Boley

doi:10.1016/j.parco.2011.04.002

Parallelization of Nullspace Algorithm for the computation of metabolic pathways

Dimitrije Jevremović, Cong T. Trinh, Friedrich Srienc, Carlos P. Sosa, Daniel L Boley

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

Abstract

Elementary mode analysis is a useful metabolic pathway analysis tool in understanding and analyzing cellular metabolism, since elementary modes can represent metabolic pathways with unique and minimal sets of enzyme-catalyzed reactions of a metabolic network under steady state conditions. However, computation of the elementary modes of a genome-scale metabolic network with 100-1000 reactions is very expensive and sometimes not feasible with the commonly used serial Nullspace Algorithm. In this work, we develop a distributed memory parallelization of the Nullspace Algorithm to handle efficiently the computation of the elementary modes of a large metabolic network. We give an implementation in C++ language with the support of MPI library functions for the parallel communication. Our proposed algorithm is accompanied with an analysis of the complexity and identification of major bottlenecks during computation of all possible pathways of a large metabolic network. The algorithm includes methods to achieve load balancing among the compute-nodes and specific communication patterns to reduce the communication overhead and improve efficiency.

Original language	English (US)
Pages (from-to)	261-278
Number of pages	18
Journal	Parallel Computing
Volume	37
Issue number	6-7
DOIs	https://doi.org/10.1016/j.parco.2011.04.002
State	Published - Jun 2011

Bibliographical note

Funding Information:
This work was partially supported by NIH Grant GM077529 , NSF Grants 0534286 and 0916750 and by the Biomedical Informatics and Computational Biology Program of the University of Minnesota, Rochester . We are grateful for resources and technical support from the University of Minnesota Supercomputing Institute, and would like to thank Can Ergenikan, David Poter and Shuxia Zhang for their help. We also thank the IBM Rochester Blue Gene Center, Cindy Mestad and Steven Westerbeck for their support. Finally, we thank Palsson’s Lab for the access to BiGG database of genome-scale metabolic networks. Appendix A

Keywords

Biochemical network
Elementary flux mode
Metabolic pathway
Nullspace Algorithm

Access

10.1016/j.parco.2011.04.002

OpenUrl availability

Full text

Cite this

@article{fd3b44241ccb481b94095c36d59f231b,

title = "Parallelization of Nullspace Algorithm for the computation of metabolic pathways",

abstract = "Elementary mode analysis is a useful metabolic pathway analysis tool in understanding and analyzing cellular metabolism, since elementary modes can represent metabolic pathways with unique and minimal sets of enzyme-catalyzed reactions of a metabolic network under steady state conditions. However, computation of the elementary modes of a genome-scale metabolic network with 100-1000 reactions is very expensive and sometimes not feasible with the commonly used serial Nullspace Algorithm. In this work, we develop a distributed memory parallelization of the Nullspace Algorithm to handle efficiently the computation of the elementary modes of a large metabolic network. We give an implementation in C++ language with the support of MPI library functions for the parallel communication. Our proposed algorithm is accompanied with an analysis of the complexity and identification of major bottlenecks during computation of all possible pathways of a large metabolic network. The algorithm includes methods to achieve load balancing among the compute-nodes and specific communication patterns to reduce the communication overhead and improve efficiency.",

keywords = "Biochemical network, Elementary flux mode, Metabolic pathway, Nullspace Algorithm",

author = "Dimitrije Jevremovi{\'c} and Trinh, {Cong T.} and Friedrich Srienc and Sosa, {Carlos P.} and Boley, {Daniel L}",

note = "Funding Information: This work was partially supported by NIH Grant GM077529 , NSF Grants 0534286 and 0916750 and by the Biomedical Informatics and Computational Biology Program of the University of Minnesota, Rochester . We are grateful for resources and technical support from the University of Minnesota Supercomputing Institute, and would like to thank Can Ergenikan, David Poter and Shuxia Zhang for their help. We also thank the IBM Rochester Blue Gene Center, Cindy Mestad and Steven Westerbeck for their support. Finally, we thank Palsson{\textquoteright}s Lab for the access to BiGG database of genome-scale metabolic networks. Appendix A ",

year = "2011",

month = jun,

doi = "10.1016/j.parco.2011.04.002",

language = "English (US)",

volume = "37",

pages = "261--278",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier",

number = "6-7",

}

TY - JOUR

T1 - Parallelization of Nullspace Algorithm for the computation of metabolic pathways

AU - Jevremović, Dimitrije

AU - Trinh, Cong T.

AU - Srienc, Friedrich

AU - Sosa, Carlos P.

AU - Boley, Daniel L

N1 - Funding Information: This work was partially supported by NIH Grant GM077529 , NSF Grants 0534286 and 0916750 and by the Biomedical Informatics and Computational Biology Program of the University of Minnesota, Rochester . We are grateful for resources and technical support from the University of Minnesota Supercomputing Institute, and would like to thank Can Ergenikan, David Poter and Shuxia Zhang for their help. We also thank the IBM Rochester Blue Gene Center, Cindy Mestad and Steven Westerbeck for their support. Finally, we thank Palsson’s Lab for the access to BiGG database of genome-scale metabolic networks. Appendix A

PY - 2011/6

Y1 - 2011/6

N2 - Elementary mode analysis is a useful metabolic pathway analysis tool in understanding and analyzing cellular metabolism, since elementary modes can represent metabolic pathways with unique and minimal sets of enzyme-catalyzed reactions of a metabolic network under steady state conditions. However, computation of the elementary modes of a genome-scale metabolic network with 100-1000 reactions is very expensive and sometimes not feasible with the commonly used serial Nullspace Algorithm. In this work, we develop a distributed memory parallelization of the Nullspace Algorithm to handle efficiently the computation of the elementary modes of a large metabolic network. We give an implementation in C++ language with the support of MPI library functions for the parallel communication. Our proposed algorithm is accompanied with an analysis of the complexity and identification of major bottlenecks during computation of all possible pathways of a large metabolic network. The algorithm includes methods to achieve load balancing among the compute-nodes and specific communication patterns to reduce the communication overhead and improve efficiency.

AB - Elementary mode analysis is a useful metabolic pathway analysis tool in understanding and analyzing cellular metabolism, since elementary modes can represent metabolic pathways with unique and minimal sets of enzyme-catalyzed reactions of a metabolic network under steady state conditions. However, computation of the elementary modes of a genome-scale metabolic network with 100-1000 reactions is very expensive and sometimes not feasible with the commonly used serial Nullspace Algorithm. In this work, we develop a distributed memory parallelization of the Nullspace Algorithm to handle efficiently the computation of the elementary modes of a large metabolic network. We give an implementation in C++ language with the support of MPI library functions for the parallel communication. Our proposed algorithm is accompanied with an analysis of the complexity and identification of major bottlenecks during computation of all possible pathways of a large metabolic network. The algorithm includes methods to achieve load balancing among the compute-nodes and specific communication patterns to reduce the communication overhead and improve efficiency.

KW - Biochemical network

KW - Elementary flux mode

KW - Metabolic pathway

KW - Nullspace Algorithm

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

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

U2 - 10.1016/j.parco.2011.04.002

DO - 10.1016/j.parco.2011.04.002

M3 - Article

AN - SCOPUS:79955706211

SN - 0167-8191

VL - 37

SP - 261

EP - 278

JO - Parallel Computing

JF - Parallel Computing

IS - 6-7

ER -

Parallelization of Nullspace Algorithm for the computation of metabolic pathways

Abstract

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this