Enumeration of Autocatalytic Subsystems in Large Chemical Reaction Networks

Abstract

Autocatalysis is an important feature of metabolic networks, contributing crucially to the self-maintenance of organisms. Autocatalytic subsystems of chemical reaction networks (CRNs) are characterized in terms of algebraic conditions on submatrices of the stoichiometric matrix. Here, we derive sufficient conditions for subgraphs supporting irreducible autocatalytic systems in the bipartite Kőnig representation of the CRN. On this basis, we develop an efficient algorithm to enumerate autocatalytic subnetworks and, as a special case, autocatalytic cores, i.e., minimal autocatalytic subnetworks, in full-size metabolic networks. The same algorithmic approach can also be used to determine autocatalytic cores only. As a showcase application, we provide a complete analysis of autocatalysis in the core metabolism of E. coli and enumerate irreducible autocatalytic subsystems of limited size in full-fledged metabolic networks of E. coli, human erythrocytes, and Methanosarcina barkeri (Archea). The mathematical and algorithmic results are accompanied by software enabling the routine analysis of autocatalysis in large CRNs.

54 Pages (35 main + 19 Supplementary Information), 16 figures

References in corpus (9)

• Array Programming with NumPy
• Modularity and community structure in networks
• Subnetwork hierarchies of biochemical pathways
• Unstable Cores are the source of instability in chemical reaction networks
• Finding All Bounded-Length Simple Cycles in a Directed Graph
• Autocatalytic Cores in Reaction Networks with Explicit Catalysis
• Stoechiometric and dynamical autocatalysis for diluted chemical reaction networks
• Constant time enumeration of perfect bipartite matchings
• BiRNe: Symbolic bifurcation analysis of reaction networks with Python