Browsing by Author "Jevremovic, Dimitrije"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    A Simple Rank Test to Distinguish Extreme Pathways from Elementary Modes in Metabolic Networks
    (2008-10-20) Jevremovic, Dimitrije; Trinh, Cong T.; Srienc, Friedrich; Boley, Daniel
    Background: Metabolic pathway analysis is a powerful tool to study the metabolic structure of a cellular metabolism that comprises an intricate network for transforming metabolites through enzyme-catalyzed reactions. The approach is based on convex analysis to solve a homogeneous system of linear equations and inequality constraints derived from the steady state operation of mass conservation of metabolites. The solutions constitute the admissible flux space known as the convex polyhedral cone. Elementary Mode and Extreme Pathway Analysis are two closely related techniques that have been developed to identify pathways spanning the admissible flux space. Both elementary modes and extreme pathways are genetically independent pathways that can support steady state operation of cellular metabolism. However, the set of extreme pathways is often a subset of elementary modes, and under certain conditions only extreme pathways are the generating edges of the polyhedral cone. Because the two techniques are closely related, it is important to develop a theoretical framework to distinguish extreme pathways from elementary modes. Results: We have found a simple algebraic test to distinguish extreme pathways from elementary modes which requires only the stoichiometry matrix. The method has been tested with published metabolic networks that have been characterized with Elementary Mode Analysis and Extreme Pathway Analysis. The identity and number of elementary modes are not altered in networks subjected to splitting every reversible reaction into two different irreversible reactions, other than the spurious futile cycles involving the new reactions themselves. However, the set of extreme pathways depends strongly on the specific treatment of the reversible reactions of the network. The application of this algebraic test for efficient computation of elementary modes in very large networks is discussed. Conclusions: Elementary modes are the complete set of genetically independent pathways of a cellular metabolism that supports steady state operation. With the simple algebraic test, we can easily identify whether a given pathway is an elementary mode or an extreme pathway before computing the complete set of pathways. This test provides a convenient way to analyze and interpret network topology with Metabolic Pathway Analysis. The algebraic test is also useful for improving the efficiency of computing elementary modes in very large metabolic networks.
  • Thumbnail Image
    Item
    Parallelization of Nullspace Algorithm for the computation of metabolic pathways
    (2010-12-14) Jevremovic, Dimitrije; Trinh, Cong T.; Srienc, Friedrich; Sosa, Carlos P.; Boley, Daniel
    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.
  • Thumbnail Image
    Item
    Scalable computation and analysis of elementary flux modes in metabolic networks
    (2013-05) Jevremovic, Dimitrije
    The full in silico reconstruction of the genome-scale cellular metabolic networks in the recent years was enabled and supported with the sequencing of genomic and transcriptomic data across numerous organism species, as well as with the growth of various biological databases. Metabolic networks provide a comprehensive overview of the cellular landscape and its phenotype prediction for the given environmental and growth conditions. Imposing the thermodynamic and steady state constraints on the reactions and internal metabolites of the given metabolic network, respectively, one still has a justifiable model which can be used to study the cellular events of interest. Metabolic pathway is introduced as a biological and mathematical concept of a subset of active reactions with a non-zero flux. In particular, elementary flux mode is a metabolic pathway with a physiological property reflected in the requirement for its enzymatic minimality. Elementary flux modes, as building blocks of the metabolic network, have numerous applications in chemical engineering and biochemistry for the study of phenotype of wild type and mutant cells. However, the large number of elementary flux modes for even medium size metabolic networks, as well as the high computational cost of the underlying Nullspace Algorithm, still present a challenge in the computation and analysis.The problem of enumerating elementary flux modes is equivalent to the one of enumerating the vertices in the degenerate polytope which still remains an open problem. Algorithm used in such enumeration is the Double Description Method, and its adaptation in the metabolic network analysis is the so-called Nullspace Algorithm. The Nullspace Algorithm is studied to identify its major bottlenecks and possible improvements in design and implementation. The reduced algebraic rank test is proposed in the event when the network has reversible reactions, and it significantly reduces the time required to check the elementarity of the candidate elementary flux mode. In the case when the network admits reversible metabolic pathway, a procedure is given to use the Nullspace Algorithm to compute one of many possible minimal generating sets, itself being a minimal subset of elementary flux modes whose linear combination can fully characterize the solution space . Initially, parallelization of the enumeration of elementary modes was proposed in the form of Combinatorial Parallel Nullspace Algorithm using MPI library routines for the message-passing distributed memory environment. Due to insufficient memory scalability and need to replicate major data structures across all the compute nodes, further steps were undertaken to attain both memory and time scalability and be able to fit larger metabolic networks to the algorithm. Global Arrays, the partitioned global address space library, was used to facilitate the development of the distributed-memory algorithm with a shared-memory view of the global memory. It allowed a merge of the concept of the shared-memory programming within a distributed-memory environment, hence allowing the computation of nearly 70 million elementary flux modes for the 83-reaction metabolic network of the Sacharomyces cerevisiae.In the event of limited memory and processor resources, a splitting of work needed to compute all elementary flux modes was needed. An earlier divide-and-conquer idea was taken and further developed into a functional implementation. It was merged with the Combinatorial Parallel Nullspace Algorithm to yield the Combined Parallel Nullspace Algorithm and demonstrated reduced memory footprint on each of the subproblems. The full set of elementary flux modes was used to enumerate multiple subsets of reactions as candidates for knockout which would collapse the metabolic network to the subset of desired elementary flux modes. Metabolic network design goals of (1) network flexibility and (2) growth-coupled production of the target chemical were incorporated within the branch-and-bound breadth-first search algorithms. Algorithms were executed on the metabolic networks of Escherichia coli and Sacharomyces cerevisae and were compared to an earlier exhaustive variation of the Berge's algorithm. Finally, a collection of ideas based on non-linear optimization methods is proposed to model the cellular phenotype with a proper objective function and infer the efficient subnetwork of the given metabolic network. Proposed methods are used with the goal of inferring reactions targeted for deletion, where the residual network will contain as many efficient elementary flux modes as possible, thus reducing the cost of running one of the previously implemented algorithms. Optimization methods aim to model the metabolic goals of the minimal energy consumption and enzymatic minimality using the L1-regularized quadratic programming framework.