Using MR-Chordless Circuits for Efficient Enumeration of Autocatalytic Cores in Large Chemical Reaction Networks

Autocatalysis is an important property of chemical reaction networks (CRNs) that is particularly prevalent in metabolic networks. A set of well-defined autocatalytic cores prominently features minimal subsystems that determine the autocatalytic capabilities. Recently, a graph-theoretic characterization has become available that enabled the enumeration of moderate size autocatalytic cores in real-life metabolic networks. Here, we improve on this approach in two ways: (1) We elaborate on algorithms for the enumeration of elementary circuits restricted to so-called MR-chordless circuits relevant for autocatalysis detection. (2) We interleave our new algorithm with tests for autocatalysis to further limit the number of circuits that need to be stored for the construction of autocatalytic cores more complex than elementary MR-chordless circuits. Combined, these innovations achieve a performance gain of several orders of magnitude and make it possible to exhaustively enumerate all autocatalytic cores in real-life metabolic reaction networks comprising several hundreds of metabolites and reactions. Importantly, we find that reaction networks with irreversible reactions contain complex autocatalytic cores comprising more than a single "cycle with an ear". Such structures exceed the established classification of autocatalytic cores for fully reversible networks into five types. Scientific contribution We developed a graph-theoretic algorithm to enumerate autocatalytic cores that is efficient enough to handle genome-scale metabolic models of various species exhaustively. To this end, we devised a novel method to enumerate elementary circuits in bipartite digraphs free of one particular type of chord, which outperforms efficient standard enumeration algorithms of elementary circuits by up to 4 orders of magnitude. We show that for CRNs comprising both reducible and irreducible reactions more complex autocatalytic cores exist than envisioned by the established classification schemes for reversible CRNs.