Enumeration Method for Structural Isomers Containing User-Defined Structures Based on Breadth-First Search Approach.

Enumeration of chemical structures satisfying given conditions is an important step in the discovery of new compounds and drugs, as well as the elucidation of the structure. One of the most frequently used conditions in the enumeration is the number of chemical elements that corresponds to the chemical formula. In this work, we propose a novel efficient enumeration algorithm, BfsStructEnum, which allows users to define desired cyclic structures and enumerates all nonredundant chemical compounds containing only defined structures as cyclic structures from a given chemical formula. To evaluate the performance, we confirm the number of enumerated structures of BfsStructEnum and MOLGEN 5.0, the latest version of a general-purpose structure generator. We also compare the computation time of BfsStructEnum with that of MOLGEN 5.0. The findings show that, given the same number of enumerated structures as MOLGEN 5.0, BfsStructEnum is significantly faster. By compressing a cyclic structure into a single node and representing chemical compounds by tree structures instead of normal graphs, the enumeration can be executed more efficiently.