Exhaustive Molecular String Enumeration for Data Augmentation and Structure Exploration

Molecular strings such as SMILES and SELFIES are linear representations of molecular graphs. Due to the inherent nonlinear structure of molecular graphs, a priori, there is no unique string representation for a given molecular graph but rather many alternative strings correspond to the same graph. This allows for the randomization of molecular strings to be used both as a means of data augmentation for training sequence-based deep learning models and, when applied to SELFIES strings, for the systematic exploration of chemical space through random string mutations and interpolations. However, established algorithms for the randomization of molecular strings only account for the randomization of the starting atom and the main and sub branches. They do not randomize the spanning trees of the molecular graphs. This results in a substantial number of overlooked molecular strings for structures with at least one ring. Herein, we present TYCHE, an algorithm for the exhaustive enumeration of all spanning trees of molecular graphs and, thus, for the generation of many more randomized molecular strings. TYCHE shows a systematic and robust performance increase when used for data augmentation, string mutation, and string interpolation. Several case studies showcase the large potential of TYCHE for impact in cheminformatics and molecular machine learning.