title: Enumerating Substituted Benzene Isomers of Tree-Like Chemical Graphs.
abstract: Enumeration of chemical structures is useful for drug design, which is one of the main targets of computational biology and bioinformatics. A chemical graph with no other cycles than benzene rings is called tree-like, and becomes a tree 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 are called the substituted benzene isomers of . When we replace each virtual atom in with a benzene ring to obtain a substituted benzene isomer, distinct isomers of 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 . Our algorithm first counts the number of all the isomers of the tree representation by a dynamic programming method. To enumerate all the isomers, for each , our algorithm then generates the th isomer by backtracking the counting phase of the dynamic programming. We also implemented our algorithm for computational experiments.
authors.forename: Jinghui
authors.initials: J
authors.lastname: Li
authors.forename: Hiroshi
authors.initials: H
authors.lastname: Nagamochi
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
mesh_terms: D000465:Algorithms; D001554:Benzene / Q000737:chemistry*; D019295:Computational Biology / Q000379:methods*; D003196:Computer Graphics; D015195:Drug Design; D007536:Isomerism; D008956:Models, Chemical
chemical_list: D001554:Benzene