Fast enumeration of non-isomorphic chemical reaction networks

Computational Methods for Systems Biology (CMSB) |

Published by Lecture Notes in Computer Science

Editor(s): Luca Bortolussi, Guido Sanguinetti

View Publication | Related File

Chemical reaction networks (CRNs) have been applied successfully to model a wide range of phenomena and are commonly used for designing molecular computation circuits. Often, CRNs with specific properties (oscillations, Turing patterns, multistability) are sought, which entails searching an exponentially large space of CRNs for those that satisfy a property. As the size of the CRNs being considered grows, so does the frequency of isomorphisms, by up to a factor N!, where N is the number of species. Accordingly, being able to generate sets of non-isomorphic CRNs within a class can lead to large computational savings when carrying out global searches. Here, we present a bijective encoding of bimolecular CRNs into novel vertex-coloured digraphs called Complex-
Species graphs. The problem of enumerating non-isomorphic CRNs can then be tackled by leveraging well-established computational methods from graph theory. In particular, we extend Nauty, the graph isomorphism tool suite by McKay. Our method is highly parallelisable and more efficient than competing approaches, and a software package (genCRN) is freely available for reuse. Non-isomorphs are generated directly by genCRN, alleviating the need to store intermediate results. We provide the first complete count of all 2-species bimolecular CRNs and extend previous known counts for classes of CRNs of special interest, such as mass-conserving and reversible CRNs.