Efficient enumeration of stereoisomers of outerplanar chemical graphs using dynamic programming

J Chem Inf Model. 2011 Nov 28;51(11):2788-807. doi: 10.1021/ci200084b. Epub 2011 Oct 25.

Abstract

Exhaustive and nonredundant generation of stereoisomers of a chemical compound with a specified constitution is an important tool for molecular structure elucidation and molecular design. It is known that many chemical compounds have outerplanar graph structures. 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. 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 recursively computes the number 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 space and correctly enumerates all of the stereoisomers in O(n³) time per stereoisomer on average and in O(n) space, where n is the number of atoms in a given structure.

Publication types

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

MeSH terms

  • Algorithms*
  • Computational Biology / methods*
  • Computational Biology / statistics & numerical data
  • Drug Design
  • Models, Chemical
  • Molecular Structure
  • Stereoisomerism