Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2009-015 (July 03, 2009)

Enumerating Stereoisomers of Tree Structured Molecules Using Dynamic Programming
by Tomoki Imada, Shunsuke Ota, Hiroshi Nagamochi, Tatsuya Akutsu

pdf File

Exhaustive and nonredundant generating stereoisomers of a chemical compound with a specified constitution is one of the important tools for molecular structure elucidation and molecular design. Tree structured molecules are the most fundamental. In this paper we deal with chemical compounds composed of carbon, hydrogen, oxygen and nitrogen atoms whose graphical structures are tree-like graphs, and consider stereoisomers caused only by asymmetry around carbon atoms. Based on dynamic programming, we propose an algorithm of generating all stereoisomers without duplication. We treat a given tree-like graph as a tree rooted at its structural center. Our algorithm first computes recursively the numbers of stereoisomers of the subgraph induced by the descendants of each vertex, and then constructs each stereoisomer by backtracking the process of computing the numbers of stereoisomers. Our algorithm correctly counts the number of stereoisomers in $O(n)$ time and correctly enumerates all the stereoisomers in $O(n)$ time per stereoisomer, where $n$ is the number of atoms in a given structure.