A dynamic programming algorithm for generating chemical isomers based on frequency vectors

We propose a dynamic programming algorithm that generates chemical isomers of a given chemical compound with cycles. We represent a chemical compound as a chemical graph and define its feature vector based on graph-theoretical descriptors. Our descriptors mainly consist of the occurrence of "edge-configuration" that captures the information of adjacent atoms such as their degrees and bond-multiplicity. We call two chemical graphs chemical isomers of each other if they have the same feature vector and share a common prescribed structure. Our proposed algorithm produces a compact representation of all chemical isomers of a given chemical graph. This representation enables efficient counting of chemical isomers without requiring explicit generation. Furthermore, our algorithm allows us to enumerate any number of isomers, even at random. For example, our compact representation for a chemical graph with 70 non-hydrogen atoms contains around 400 arcs in which [Formula: see text] chemical isomers are embedded. The proposed algorithm serves as a powerful tool for accelerating chemical compound exploration, particularly in drug discovery and material science, where identifying novel molecular structures is critical. By efficient enumeration of isomers, our approach enhances the search space exploration for target chemical compounds, facilitating advancements in molecular design.