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.

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

References in corpus (13)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Array Programming with NumPy
• Modularity and community structure in networks
• Hierarchical organization of modularity in metabolic networks
• Subnetwork hierarchies of biochemical pathways
• Generalized mass action systems: Complex balancing equilibria and sign vectors of the stoichiometric and kinetic-order subspaces
• Finding All Bounded-Length Simple Cycles in a Directed Graph
• Unstable Cores are the source of instability in chemical reaction networks
• Good and bad children in metabolic networks
• 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
• Autocatalytic Cores in Reaction Networks with Explicit Catalysis