Parallel extreme pathway computation for metabolic networks

We parallelized the serial extreme pathways algorithm presented by Schilling et al., in J. Theor. Biol. 203 (2000) using the message passing interface (MPI). The parallel algorithm exhibits super-linear scalability because the number of independence tests performed decreases as the number of MPI nodes increases. A subsystem of the metabolic network of Escherichia coli with 140 reactions and 96 metabolites (without preprocessing) is used as a benchmark. The extreme pathways of this system are computed in under 280 seconds using 70 2.4 GHz Intel Pentium-IV CPUs with Myrinet interconnection among the dual-CPU nodes of the Linux cluster.