Enumerating Naphthalene Isomers of Tree-like Chemical Graphs
Fei He, Akiyoshi Hanai, Hiroshi Nagamochi, Tatsuya Akutsu · 2016
In this paper, we consider the problem of enumerating naphthalene isomers, where enumeration of isomers is important for drug design. A chemical graph G with no other cycles than naphthalene rings is called tree-like, and becomes a tree T possibly with multiple edges if we contract each naphthalene ring into a single virtual atom of valence 8. We call tree T the tree representation of G. There may be more than one tree-like chemical graphs whose tree representations equal to T, which are called naphthalene isomers of T. We present an efficient algorithm that enumerates all naphthalene isomers of a given tree representation. Our algorithm first counts the number of all the naphthalene isomers using dynamic programming, and then for each k, generates the k-th isomer by backtracking the counting computation. In computational experiment, we compare our method with MolGen, a state-of-the-art enumeration tool, and it is observed that our program enumerates the same number of naphthalene isomers within extremely shorter time, which proves that our algorithm is effectively built.