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-sized autocatalytic cores in real-life metabolic networks. Such an approach relies on enumerating and properly assembling elementary circuits in the bipartite graph associated to a CRN. 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. These circuits do not have a chord from a Metabolite to a Reaction vertex, and are the only candidates to find autocatalytic cores. (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 hundred 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 contributionWe developed a new graph-theoretic algorithm for enumerating autocatalytic cores that can handle large genome-scale metabolic models. Implemented in the Python program autogatito, it is up to four orders of magnitude faster than previous methods. Applications to large metabolic network models that involve both reversible and nonreversible reactions reveal that more complex autocatalytic cores exist than predicted by existing classification schemes for reversible reactions.