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
$G$
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,\ldots, f$
, our algorithm then generates the
$k$
th isomer by backtracking the counting phase of the dynamic programming. We also implemented our algorithm for computational experiments.