Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2010-018 (December 16, 2010)
Efficient Enumeration of Stereoisomers of Outerplanar Chemical Graphs Using Dynamic Programming
by Tomoki Imada, Shunsuke Ota, Hiroshi Nagamochi, Tatsuya Akutsu
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.
In this paper we deal with chemical compounds composed of carbon, hydrogen, oxygen and nitrogen atoms
whose graphical structures are outerplanar,
and consider stereoisomers caused only by asymmetry around carbon atoms.
It is known that many chemical compounds have outerplanar graph structures.
Based on dynamic programming, we propose an algorithm of generating all stereoisomers
without duplication.
We treat a given outerplanar graph as a graph 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^3)$ time per stereoisomer on average, where $n$ is the number of atoms in a given structure.