Enumerating Substituted Benzene Isomers of Tree-Like Chemical Graphs

Enumeration of chemical structures is useful for drug design, which is one of the main targets of computational biology and bioinformatics. A chemical graph C with no other cycles than benzene rings is called tree-like, and becomes a tree T possibly with multiple edges if we contract each benzene ring into a single virtual atom of valence 6. All tree-like chemical graphs with a given tree representation T are called the substituted benzene isomers of T. When we replace each virtual atom in T with a benzene ring to obtain a substituted benzene isomer, distinct isomers of T are caused by the difference in arrangements of atom groups around a benzene ring. In this paper, we propose an efficient algorithm that enumerates all substituted benzene isomers of a given tree representation T. Our algorithm first counts the number f of all the isomers of the tree representation by a dynamic programming method. To enumerate all the isomers, for each k = 1,2, ... , f, our algorithm then generates the 6th isomer by backtracking the counting phase of the dynamic programming. We also implemented our algorithm for computational experiments.