Using聽Oriented Matroids To Understand Metabolic Networks
Genome scale models of cellular metabolism involve thousands of reactions, even for relatively simple model organisms such as聽E. coli.聽 Given a stoichiometric matrix, S, one could parametrize a system of thousands of ODEs for the metabolite concentrations: x' = S*v(x;k).聽 Instead, models typically avoid identifying parameters by assuming that metabolite concentrations are in steady state during growth: 0=S*v.聽 The resulting equation for the rates is underdetermined.聽 However, one can limit solutions by solving a linear program to maximize growth-related reactions: max c^T*v s.t. 0=S*v and v_{min,i} <= v_i <= v_{max,i}.聽
Oriented matroids have been used to understand several aspects of this problem.聽 This is because oriented matroids generalize objects such as directed reaction graphs and sign patterns of the columns of the stoichiometric matrix, S.聽 Furthermore, matroids have proven useful in algorithms for several reasons.聽 Matroids have simpler structure than the objects which they abstract, they have dozens of equivalent axiom systems (independent sets, bases, circuits, etc.), and they are in some sense precisely those objects for which the greedy algorithm is optimal.