Identification of Conserved Moieties in Metabolic Networks by Graph Theoretical Analysis of Atom Transition Networks
Conserved moieties give rise to pools of metabolites with constant total concentration and dependent individual concentrations ., These constant metabolite pools often consist of highly connected cofactors that are distributed throughout a metabolic network ., Representative examples from energy metabolism include the AMP and NAD moieties 1 , 2 ., Changes in concentration ratios within these cofactor pools affect thermodynamic and mass action kinetic driving forces for all reactions they participate in ., Moiety conservation therefore imposes a purely physicochemical form of regulation on metabolism that is mediated through changes in concentration ratios within constant metabolite pools ., Reich and Sel’kov likened conserved moieties to turning wheels that are “geared into a clockwork” 2 ., They described the thermodynamic state of energy metabolism as “open flow through a system closed by moiety conservation” ., Identification of conserved moieties in metabolic networks has helped elucidate complex metabolic phenomena including synchronisation of glycolytic oscillations in yeast cell populations 3 and the function of glycosomes in the African sleeping sickness parasite Trypanosoma brucei 4 ., It has also been shown to be relevant for drug development 4 , 5 ., Identification of conserved moieties has been of interest to the metabolic modelling community for several decades 6 , 7 ., It is particularly important for dynamic modelling 8 and metabolic control analysis 9 where metabolite concentrations are explicitly modelled ., Moiety conservation relations provide a sparse , physically meaningful description of concentration dependencies in a metabolic network ., They can be used to eliminate redundant metabolite concentrations as the latter can be derived from the set of independently varying metabolite concentrations ., Doing so facilitates simulation of metabolic networks and is in fact required for many computational modelling methods 6 , 7 ., Mathematically , moiety conservation gives rise to a stoichiometric matrix with linearly dependent rows ., The left null space of the stoichiometric matrix therefore has nonzero dimension ( see Theoretical Framework , Section Moiety vectors ) ., Vectors in the left null space , hereafter referred to as conservation vectors , can be divided into several interrelated sets based on their numerical properties and biochemical meaning ( Fig 1 ) ., Moiety vectors constitute a subset of conservation vectors with a distinct biochemical interpretation ., Each moiety vector represents conservation of a particular metabolic moiety ., Elements of a moiety vector correspond to the number of instances of a conserved moiety in metabolites of a metabolic network ., As moieties are discrete quantities , moiety vectors are necessarily nonnegative integer vectors ., Methods exist to compute conservation vectors based only on the stoichiometric matrix of a metabolic network ., These methods compute different types of bases for the left null space of the stoichiometric matrix ( see S1 Appendix for mathematical definitions ) ., Each method draws basis vectors from a particular set of conservation vectors ( Fig 1 ) ., There is a tradeoff between the computational complexity of these methods and the biochemical interpretability of the basis vectors they return ., At the low end of the computational complexity spectrum are linear algebraic methods such as singular value decomposition ., Other methods , such as Householder QR factorisation 7 or sparse LU factorisation 10 are more efficient for large stoichiometric matrices ., These methods construct a linear basis for the left null space from real-valued conservation vectors ., Though readily computed , these vectors are also the most difficult to interpret as they generally contain negative and noninteger elements ., Schuster and Höfer 11 introduced the use of vertex enumeration algorithms to compute the extreme rays of the positive orthant of the left null space ., They referred to these extreme rays as “extreme semipositive conservation relations” ., Famili and Palsson 12 later referred to them as “metabolic pools” and the set of all extreme rays as “a convex basis for the left null space” ., Like moiety vectors , extreme rays are nonnegative integer vectors ., They are therefore readily interpreted in terms of constant metabolite pools ., However , extreme rays can currently only be computed for relatively small metabolic networks due to the computational complexity of vertex enumeration algorithms 13 ., Moreover , the set of extreme rays is not identical to the set of moiety vectors ( Fig 1 ) ., Schuster and Hilgetag 14 presented examples of extreme rays that did not represent moiety conservation relations , as well as moiety vectors that were not extreme rays ., Moiety vectors are a property of a metabolic network while extreme rays are a property of its stoichiometric matrix ., Multiple metabolic networks could in theory have the same stoichiometric matrix , despite consisting of different sets of metabolites and reactions ., These networks would all have the same set of extreme rays , but could have different sets of moiety vectors ., Schuster and Hilgetag 14 published an extension to the vertex enumeration algorithm in 11 to compute the set of all nondecomposable nonnegative integer vectors in the left null space of a stoichiometric matrix ., This set is guaranteed to contain all nondecomposable moiety vectors for a particular metabolic network as subset ( Fig 1 ) ., However , it is impossible to identify the subset of moiety vectors without information about the atomic structure of metabolites ., Alternatives to vertex enumeration have been proposed to speed up computation of biochemically meaningful conservation vectors , e . g . , 15–17 ., Most recently , De Martino et al . 17 published a novel method to compute a nonnegative integer basis for the left null space of a stoichiometric matrix ., This method 17 relies on stochastic algorithms , without guaranteed convergence , but that were empirically shown to perform well even on large networks ., Like extreme rays , the nonnegative integer vectors computed with this method are not necessarily moiety vectors ( Fig 1 ) ., In general , methods to analyse stoichiometric matrices are not suited to specifically compute moiety vectors ., Computation of moiety vectors requires information about the atomic composition of metabolites ., To our knowledge , only one method has previously been published to specifically compute moiety vectors for metabolic networks 18 ., This method was based on nonnegative integer factorisation of the elemental matrix; a numerical representation of metabolite formulas ., Nonnegative integer factorisation of a matrix is at least NP-hard 19 and no polynomial time algorithm is known to exist for this problem ., Moreover , only the chemical formula but not the atomic identities of the conserved moieties can be derived from this approach ., Identifying the atoms that belong to each moiety requires additional information about the fate of atoms in metabolic reactions ., This information is not contained in a stoichiometric matrix ., Here , we propose a novel method to identify conserved moieties in metabolic networks ., Our method is based on the premise that atoms within the same conserved moiety follow identical paths through a metabolic network ., Given data on which substrate atoms map to which product atoms in each metabolic reaction , the paths of individual atoms through a metabolic network can be encoded in an atom transition network ., Until recently , the necessary data were difficult to obtain but relatively efficient algorithms have now become available to predict atom mappings in metabolic reactions 20–22 ., These algorithms have made it possible to construct atom transition networks for large metabolic networks ., Unlike metabolic networks , atom transition networks are amenable to analysis with efficient graph theory algorithms ., Here , we take advantage of this fact to identify conserved moieties in metabolic networks in polynomial time ., Furthermore , starting from atom transition networks allows us to associate each conserved moiety with a specific group of atoms in a subset of metabolites in a metabolic network ., This work combines elements of biochemistry , linear algebra and graph theory ., We have made an effort to accommodate readers from all fields ., The main text consists of informal descriptions of our methods and results , accompanied by illustrative examples and a limited number of mathematical equations ., Formal definitions of italicised terms are given in supporting file S1 Appendix ., We precede our results with a section on the theoretical framework for this work , where we introduce key concepts and notation used in the remainder of the text ., A metabolic network consists of a set of metabolites that interconvert via a set of metabolic reactions ., Metabolic networks in living beings are open systems that exchange mass and energy with their environment ., For modelling purposes , the boundary between system and environment can be defined by introducing a set of metabolite sources and sinks collectively known as exchange reactions ., Unlike internal reactions , exchange reactions are artificial constructs that do not conserve mass or charge ., The topology of a metabolic network can be represented in several ways ., Here , we use metabolic maps and stoichiometric matrices ., A metabolic map for a small example metabolic network is shown in Fig 2 ., This example will be used throughout this section to demonstrate key concepts relevant to this work ., A stoichiometric matrix for an open metabolic network with m metabolites and n reactions is denoted by S ∈ R m × n ., Each row of S represents a metabolite and each column a reaction such that element Sij is the stoichiometric coefficient of metabolite i in reaction j ., Coefficients are negative for substrates and positive for products ., Substrates and products in reversible reactions are defined by designating one direction as forward ., The stoichiometric matrix can be written as, S = N , B , ( 1 ), where N ∈ Z m × u consists of columns representing internal ( mass balanced ) reactions and B ∈ R m × ( n - u ) consists of columns representing exchange reactions ( mass imbalanced ) ., Note that N represents a metabolic network that is closed to the environment ., In what follows we will refer to N as the internal stoichiometric matrix , B as the exchange stoichiometric matrix , and S as the total stoichiometric matrix ., The total stoichiometric matrix for the example metabolic network in Fig 2 is given in Table 1 ., Stoichiometric matrices are incidence matrices for generalised graphs known as hypergraphs 24 ., Hypergraphs contain hyperedges that can connect more than two nodes ., The metabolic map in Fig 2 is a planar visualisation of a hypergraph with one hyperedge , connecting four metabolites ., A graph edge that only connects two nodes is a special instance of a hyperedge ., Apart from the occasional isomerisation reaction , metabolic reactions involve more than two metabolites ., As a result , they cannot be represented as graph edges without loss of information ., Metabolic networks are therefore represented as hypergraphs where nodes represent metabolites and hyperedges represent reactions ., Since reactions have a designated forward direction , they are directed hypergraphs ., Representing metabolic networks as hypergraphs has the advantage of conserving basic structure and functional relationships ., The disadvantage is that many graph theoretical algorithms are not applicable to hypergraphs 24 ., An internal stoichiometric matrix N ∈ Z m × u for a closed metabolic network is always row-rank deficient ,, i . e ., , rank ( N ) < m 11 ., The left null space of N , denoted by N ( N T ) , therefore has finite dimension given by dim ( N ( N T ) ) = m - rank ( N ) ., The left null space holds all conservation vectors for a stoichiometric matrix 8 ., The number of linearly independent conservation vectors for a closed metabolic network is dim ( N ( N T ) ) ., The total stoichiometric matrix S for an open metabolic network has a greater rank than the internal stoichiometric matrix N for the corresponding closed metabolic network ( e . g . , Table 1 ) ,, i . e ., , rank ( N ) < rank ( S ) ., Consequently , dim ( N ( S T ) ) < dim ( N ( N T ) ) , meaning that there are fewer linearly independent conservation vectors for an open metabolic network than the corresponding closed network ., This is consistent with physical reality , since mass can flow into and out of open networks but is conserved within closed networks ., All quantities that are conserved in an open metabolic network are also conserved in the corresponding closed network ., That is , if z is a conservation vector for an open metabolic network S , such that ST z = 0 , then z is also a conservation vector for the corresponding closed network N , and NT z = 0 , since S = N , B ., The set of conservation relations for an open network is therefore a subset of all conservation relations for the corresponding closed network ,, i . e ., , N ( S T ) ⊆ N ( N T ) ., In what follows we will mainly be concerned with the larger set of conservation relations for a closed metabolic network ., Schuster and Hilgetag 14 defined a moiety vector l1 as a nonnegative integer vector in the left null space of a stoichiometric matrix ,, i . e ., ,, N T l 1 = 0 , ( 2 ) l 1 ∈ N 0 m ., ( 3 ), In addition , they defined l1 to be a maximal moiety vector if it cannot be decomposed into two other vectors l2 and l3 that satisfy Eqs 2 and 3 ,, i . e ., , if, l 1 ≠ α 2 l 2 + α 3 l 3 , ( 4 ), where α 2 , α 3 ∈ N + ., We propose a more specific definition ., The properties above define increasingly small sets of conservation vectors ( Fig 1 ) ., Eq 2 defines the set of all conservation vectors ., Addition of Eq 3 defines the set of nonnegative integer conservation vectors and addition of Eq 4 defines the set of nonnegative integer conservation vectors that are nondecomposable ., Although this set includes all nondecomposable moiety vectors as subset it is not equivalent ( Fig 1 ) ., To define the set of moiety vectors we require a fourth property ., We define l1 to be a moiety vector if it satisfies Eqs 2 and 3 and represents conservation of a specific metabolic moiety ,, i . e ., , an identifiable group of atoms in network metabolites ., Element l1 , i should correspond to the number of instances of the conserved moiety in metabolite, i . We define l1 to be a nondecomposable moiety vector if it satisfies condition 4 and a composite moiety vector if it does not ., Nondecomposable moiety vectors for the DOPA decarboxylase reaction from the example metabolic network in Fig 2 are given in Table 2a ., For comparison , conservation vectors computed with existing methods for conservation analysis of metabolic networks are given in Table 2b–2d ., In general , these vectors do not represent moiety conservation ., Metabolic reactions conserve mass and chemical elements ., Therefore , there must exist a mapping from each atom in a reactant metabolite to a single atom of the same element in a product metabolite ., An atom transition is a single mapping from a substrate to a product atom ., An atom transition network contains information about all atom transitions in a metabolic network ., It is a mathematical structure that enables one to trace the paths of each individual atom through a metabolic network ., An atom transition network can be generated automatically from a stoichiometric matrix for a metabolic network and atom mappings for internal reactions ., The atom transition network for the DOPA decarboxylase reaction from the example metabolic network in Fig 2 is shown in Fig 3 ., Unlike metabolic networks , atom transition networks are graphs since every atom transition ( edge ) connects exactly two atoms ( nodes ) ., They are directed graphs since every atom transition has a designated direction that is determined by the directionality of the parent metabolic reaction ,, i . e ., , the designation of substrates and products ., Because atom transition networks are graphs , they are amenable to analysis with efficient graph algorithms that are not generally applicable to metabolic networks due to the presence of hyperedges 24 ., We will demonstrate our method by identifying conserved moieties in the simple dopamine synthesis network DAS in Fig 4 . This network consists of 11 metabolites , four internal reactions and seven exchange reactions ., The total stoichiometric matrix S = N , B is given in Table 3 . The internal stoichiometric matrix N is row rank deficient with rank ( N ) = 4 . The dimension of the left null space is therefore dim ( N ( N T ) ) = 7 , meaning that there are seven linearly independent conservation vectors for the closed metabolic network ., Our analysis of an atom transition network for DAS will conclude with the computation of seven linearly independent moiety vectors that span N ( N T ) ., To compute these vectors we require the internal stoichiometric matrix in Table 3 and atom mappings for the four internal reactions ., Here , we used algorithmically predicted atom mappings 20 ., These data are required to generate an atom transition network for DAS ( see Methods , Section Generation of atom transition networks ) ., By graph theoretical analysis of this atom transition network we derive the first of two alternative representations of moiety conservation relations which we term moiety graphs ., Nodes in a moiety graph represent separate instances of a conserved moiety ., Each node is associated with a specific set of atoms in a particular metabolite ., The second representation of moiety conservation relations are the moiety vectors which can be derived from moiety graphs in a straightforward manner ., Moiety vectors computed with our method are therefore associated with specific atoms via moiety graphs ., To identify all conserved moieties in DAS we require an atom transition network for all atoms regardless of element but for demonstration purposes we will initially focus only on carbon atoms ., A carbon atom transition network for DAS is shown in Fig 5a ., Our working definition of a conserved moiety is a group of atoms that follow identical paths through a metabolic network ., To identify conserved moieties , we therefore need to trace the paths of individual atoms and determine which paths are identical ., The paths of individual atoms through the carbon atom transition network for DAS can be traced by visual inspection of Fig 5a ., For example , we can trace a path from C1 in L-phenylalanine to C7 in dopamine via C3 in L-tyrosine and C8 in levodopa ., This path is made up of atom transitions in reactions R1 , R2 , and R3 from Fig 4 . In graph theory terms , these four carbon atoms and the atom transitions that connect them constitute a connected component 25 or , simply , a component of the directed graph representing the carbon atom transition network for DAS ., A directed graph is said to be connected if a path exists between any pair of nodes when edge directions are ignored ., A component of a directed graph is a maximal connected subgraph ., In total , the carbon atom transition network for DAS in Fig 5a consists of 18 components ., The paths of the first eight carbon atoms ( C1–C8 ) in L-phenylalanine are identical in the sense that they include the same number of atoms in each metabolite and the same number of atom transitions in each reaction ., In graph theory terms , the components containing C1–C8 in L-phenylalanine are isomorphic ., An isomorphism between two graphs is a structure preserving vertex bijection 25 ., The definition of isomorphism varies for different types of graphs as they have different structural elements that need to be preserved ., An isomorphism between two simple graphs is a vertex bijection that preserves the adjacency and nonadjacency of every node , i . e . , its connectivity ., An isomorphism between two simple directed graphs must also preserve edge directions ., We define an isomorphism between two components of an atom transition network as a vertex bijection that preserves the metabolic identity of every node ., The nature of chemical reactions ensures that all other structural elements are preserved along with metabolic identities , including the connectivity of atoms and the number , directions and reaction identities of atom transitions ., The 18 components of the carbon atom transition network for DAS in Fig 5a can be divided into three sets , where every pair of components within each set is isomorphic ., An isomorphism between two components of an atom transition network is a one-to-one mapping between atoms in the two components ., For example , the isomorphism between the two left-most components in Fig 5a maps between C1 and C2 in L-phenylalanine , C3 and C2 in L-tyrosine , C8 and C7 in L-DOPA , and C7 and C8 in dopamine ., We say that two atoms are equivalent if an isomorphism maps between them ., We note that our definition of isomorphism only allows mappings between atoms with the same metabolic identity ., Two atoms can therefore only be equivalent if they are in the same metabolite ., Equivalent atoms follow identical paths through a metabolic network and therefore belong to the same conserved moiety ., In general , we define a conserved moiety to be a maximal set of equivalent atoms in an atom transition network ., To identify conserved moieties , we must therefore determine isomorphisms between components of an atom transition network to identify maximal sets of equivalent atoms ., The first eight carbon atoms ( C1–C8 ) in L-phenylalanine are equivalent ., They are therefore part of the same conserved moiety , which we denote λ1 ., The last eight carbon atoms ( C2–C9 ) in L-tyrosine are likewise part of the same conserved moiety ., They make up another instance of the λ1 moiety ., The λ1 moiety is conserved between L-phenylalanine and L-tyrosine in reaction R1 , between L-tyrosine and levodopa in reaction R2 , and between levodopa and dopamine in reaction R3 ., Each of the four metabolites contains one instance of the λ1 moiety ., The path of this moiety through DAS defines its conservation relation ., This brings us to our first representation of moiety conservation relations , which we term moiety graphs ., Moiety graphs are obtained from atom transition networks by merging a set of isomorphic components into a single graph ., Moiety graphs for the three carbon atom moieties in DAS are shown in Fig 5b ., Four additional moieties were identified by analysis of an atom transition network for DAS that included all atoms regardless of element ., All seven moiety graphs are shown in Fig 6 ., Atoms belonging to each node in the moiety graphs are highlighted in Fig 4 . The second way to represent moiety conservation relations is as moiety vectors ., Above we defined a moiety vector as a conservation vector lk where element lk , i corresponds to the number of instances of moiety k in metabolite i of a metabolic network ( see Section Moiety vectors in Theoretical Framework ) ., We can now make this definition exact by relating moiety vectors to moiety graphs ., Each instance of a conserved moiety is represented as a node in its moiety graph ., Element lk , i of a moiety vector therefore corresponds to the number of nodes in moiety graph λk that represent moieties in metabolite i ., Moiety vectors are readily derived from moiety graphs by counting the number of nodes in each metabolite ., Moiety vectors for DAS were derived from the moiety graphs in Fig 6 ., The seven moiety vectors are given as columns of the moiety matrix L ∈ Z 11 × 7 in Table 4 . These seven vectors are linearly independent and therefore span all seven dimensions of N ( N T ) ., The moiety matrix L is therefore a moiety basis for the left null space ., Atom transition networks are generated from atom mappings for internal reactions of metabolic networks ., However , atom mappings for metabolic reactions are not necessarily unique ., Computationally predicted atom mappings , as used here , are always associated with some uncertainty ., In addition , there can be biochemical variability in atom mappings , in particular for metabolites containing symmetric atoms ., All reactions of the O2 molecule , for example , have at least two biochemically equivalent atom mappings since the two symmetric oxygen atoms map with equal probability to connected atoms ., Different atom mappings give rise to different atom transition networks that may contain different moiety conservation relations ., For the most part , we found that varying the set of input atom mappings did not affect the number of computed moiety conservation relations , only their atomic structure ., An important exception was when atom mappings between the same pair of metabolites varied between reactions in the same metabolic network ., The same pair of metabolites often exchange atoms in multiple reactions throughout the same metabolic network ., Common cofactors such as ATP and ADP , for example , exchange atoms in hundreds of reactions in large metabolic networks 26 ., In the dopamine synthesis network , DAS in Fig 4 , O2 and H2O exchange an oxygen atom in two reactions , R1 and R2 ., Since the two oxygen atoms of O2 are symmetric , there are four possible combinations of oxygen atom mappings for these two reactions ., Each combination gives rise to a different oxygen transition network as shown in Fig 7 ., Two of these oxygen transition networks , shown in Fig 7a and 7b , contain two moiety conservation relations each , λ6 and λ7 , which are shown in Fig 7c ., The other two oxygen transition networks , shown in Fig 7d and 7e , contain only one moiety conservation relation each , λ8 , which is shown in Fig 7f ., The DAS atom transition network considered in the previous section was generated with the oxygen atom mappings in Fig 7a and thus contained the two moiety conservation relations λ6 and λ7 ( see Fig 6 ) ., An atom transition network generated with the atom mappings in Fig 7d or 7e would contain the single moiety conservation relation λ8 instead of these two ., What distinguishes the oxygen transition networks in Fig 7d and 7e is that the oxygen atom in O2 that maps to H2O varies between the two reactions R1 and R2 ., The atom transition network for DAS therefore contains one less moiety conservation relation if the atom mapping between this recurring metabolite pair varies between reactions ., The moiety matrix for these alternative atom transition networks ,, L = l 1 , l 2 , l 3 , l 4 , l 5 , l 8 , ( 5 ), only contains six linearly independent columns and is therefore not a basis for the seven dimensional left null space of N . The vector representation of moiety graph λ8 is, l 8 T = 0 1 2 2 0 0 0 0 2 1 0 ., ( 6 ), We note that l8 = l6 + l7 where, l 6 T = 0 1 2 2 0 0 0 0 1 0 0 , ( 7 ) l 7 T = 0 0 0 0 0 0 0 0 1 1 0 , ( 8 ), from Table 4 . The moiety vector l8 therefore represents a composite moiety ., It does not meet the definition of a nondecomposable moiety vector in Eq 4 . This example shows that variable atom mappings between recurring metabolite pairs may cause multiple nondecomposable moiety conservation relations to be joined together into a single composite moiety conservation relation ., We formulated an optimisation problem , described in Methods , Section Decomposition of moiety vectors , to decompose composite moiety vectors ., Solving this problem for the composite moiety vector l8 yields the two nondecomposable components l6 and l7 ., We applied our method to identify conserved moieties in three metabolic networks of increasing size ., The networks , listed from smallest to largest , were the dopamine synthesis network , DAS in Fig 4 , the E . coli core metabolic network , iCore 27 , and an atom mapped subset of the generic human metabolic reconstruction , Recon 2 26 which we refer to here as subRecon ., The dimensions of the three networks are given in Table 5a ., Further descriptions are provided in Methods , Section Metabolic networks ., There are seven linearly independent conservation relations for the closed DAS network , 11 for iCore , and 351 for subRecon ., Atom transition networks were generated using algorithmically predicted atom mappings 20 as described in Methods , Section Generation of atom transition networks ., Seven , ten and 345 moiety conservation relations were identified in the predicted atom transition network for DAS , iCore and subRecon , respectively ( Table 5b ) ., Characterisation of identified moieties revealed some trends ( Fig 8 ) ., We found a roughly inverse relationship between the frequency of a moiety , defined as the number of instances , and the size of that moiety , defined as the number of atoms per instance ., We also found a relationship between moiety size , frequency and classification ., Internal moieties tended to be large and infrequent , occurring in a small number of closely related secondary metabolites , e . g . , the 35 atom AMP moiety found in the three iCore metabolites AMP , ADP and ATP ., Integrative moieties were usually small and frequent while transitive moieties were intermediate in both size and frequency ., The smallest moieties consisted of single atoms ., These were often highly frequent , occurring in up to 62/72 iCore metabolites and 2 , 472/2 , 970 subRecon metabolites ., These results indicate a remarkable interconnectivity between metabolites at the atomic level ., Due to their frequency , single atom moieties accounted for a large portion of atoms in each metabolic network ., Single atom moieties accounted for nearly half ( 791/1 , 697 ) of all atoms in iCore , and approximately two thirds ( 104 , 268/153 , 298 ) of all atoms in subRecon ., Moiety matrices derived from the predicted atom transition networks for iCore and subRecon did not span the left null spaces of their respective stoichiometric matrices , indicating that they might contain composite moiety vectors ., Using the method described in Methods , Section Decomposition of moiety vectors , we found two composite moiety vectors in the moiety matrix for iCore , and 10 in the one for subRecon ., Decomposition of these vectors yielded three new nondecomposable moiety vectors for iCore and 18 for subRecon ( Table 5b ) ., The 11 nondecomposable moiety vectors for iCore were linearly independent ., They therefore comprised a basis for the 11 dimensional left null space of N for iCore ., The 353 nondecomposable moiety vectors for subRecon , on the other hand , were not linearly independent and only spanned 347 out of 351 dimensions in the left null space of S for subRecon ., This indicated that there existed conservation relations for subRecon that were independent of atom conservation ., Schuster and Höfer , citing earlier work by Aris 28 and Corio 29 , noted the importance of considering electron conservation in addition to atom conservation 11 ., Unfortunately , it is not as straightforward to map electrons as atoms and no formalism currently exists for electron mappings ., As a result , electron conservation relations cannot be computed with the current version of our algorithm ., We therefore computed electron conservation relations for subRecon by decomposing the electron vector with the method described in Methods , Section Decomposition of moiety vectors ., An electron vector for a metabolic network with m metabolites is a vector e ∈ N m where ei is the total number of electrons in metabolite i ., Decomposition of e for subRecon yielded 11 new conservation vectors ., When combined , the 11 electron vectors and the 353 fully decomposed moiety vectors for subRecon ( Table 5b ) spanned the left null space of the subRecon stoichiometric matrix ., Internal moieties define pools of metabolites with constant total conce
Conserved moieties are groups of atoms that remain intact in all reactions of a metabolic network ., 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 , the vectors returned by existing algorithms do not , in general , represent conservation of a specific moiety with a defined atomic structure ., Here , we show that identification of conserved moieties requires data on reaction atom mappings in addition to stoichiometry ., We present a novel method to identify conserved moieties in metabolic networks by graph theoretical analysis of their underlying atom transition networks ., Our method returns the exact group of atoms belonging to each conserved moiety as well as the corresponding vector in the left null space of the stoichiometric matrix ., It can be implemented as a pipeline of polynomial time algorithms ., Our implementation completes in under five minutes on a metabolic network with more than 4 , 000 mass balanced reactions ., The scalability of the method enables extension of existing applications for moiety conservation relations to genome-scale metabolic networks ., We also give examples of new applications made possible by elucidating the atomic structure of conserved moieties .
Conserved moieties are transferred between metabolites in internal reactions of a metabolic network but are not synthesised , degraded or exchanged with the environment ., The total amount of a conserved moiety in the metabolic network is therefore constant over time ., Metabolites that share a conserved moiety have interdependent concentrations because their total amount is constant ., Identification of conserved moieties results in a concise description of all concentration dependencies in a metabolic network ., The problem of identifying conserved moieties has previously been formulated in terms of the stoichiometry of metabolic reactions ., Methods based on this formulation are computationally intractable for large networks ., We show that reaction stoichiometry alone gives insufficient information to identify conserved moieties ., By first incorporating additional data on the fate of atoms in metabolic reactions , we developed and implemented a computationally tractable algorithm to identify conserved moieties and their atomic structure .
oxygen, applied mathematics, metabolic networks, simulation and modeling, algorithms, mathematics, metabolites, algebra, network analysis, carbon, molecular biology techniques, research and analysis methods, cell labeling, computer and information sciences, vector spaces, chemistry, graph theory, molecular biology, biochemistry, metabolic labeling, linear algebra, biology and life sciences, physical sciences, metabolism, chemical elements