Polynomial Time Identification of Conserved Moieties in Metabolic Networks

Identification of conserved moieties gives insight into the structure and function of metabolic networks and facilitates metabolic modelling. All moiety conservation relations can be represented as nonnegative integer vectors in the left null space of the stoichiometric matrix corresponding to a biochemical network. Algorithms exist to compute such vectors based only on reaction stoichiometry but their computational complexity has limited their application to relatively small metabolic networks. Moreover, existing algorithms give no information about the atomic structure of conserved moieties. Here, we present a novel algorithm to identify conserved moieties in metabolic networks by graph theoretical analysis of their underlying atom transition networks. Our algorithm returns the exact group of atoms belonging to each conserved moiety as well as the corresponding vector in the left null space of the input stoichiometric matrix. Its scales in polynomial time with the number of network reactions, completing in approximately two hours on a network with more than 4,000 internal reactions. The scalability of the algorithm enables extension of existing applications for moiety conservation relations to genome-scale metabolic networks. Elucidation of the atomic structure of conserved moieties also opens the door to novel applications, in particular in stable isotope assisted metabolic flux analysis.