Enumerating Substituted Benzene Isomers of Tree-Like Chemical Graphs

IEEE/ACM Trans Comput Biol Bioinform. 2018 Mar-Apr;15(2):633-646. doi: 10.1109/TCBB.2016.2628888. Epub 2016 Nov 15.

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.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms
  • Benzene / chemistry*
  • Computational Biology / methods*
  • Computer Graphics
  • Drug Design
  • Isomerism*
  • Models, Chemical*

Substances

  • Benzene