論文

査読有り
2011年11月

Efficient Enumeration of Stereoisomers of Outerplanar Chemical Graphs Using Dynamic Programming

JOURNAL OF CHEMICAL INFORMATION AND MODELING
  • Tomoki Imada
  • ,
  • Shunsuke Ota
  • ,
  • Hiroshi Nagamochi
  • ,
  • Tatsuya Akutsu

51
11
開始ページ
2788
終了ページ
2807
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1021/ci200084b
出版者・発行元
AMER CHEMICAL SOC

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(3)) time per stereoisomer on average and in O(n) space, where n is the number of atoms in a given structure.

リンク情報
DOI
https://doi.org/10.1021/ci200084b
DBLP
https://dblp.uni-trier.de/rec/journals/jcisd/ImadaONA11
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000297275000002&DestApp=WOS_CPL
URL
http://dblp.uni-trier.de/db/journals/jcisd/jcisd51.html#journals/jcisd/ImadaONA11
ID情報
  • DOI : 10.1021/ci200084b
  • ISSN : 1549-9596
  • eISSN : 1549-960X
  • DBLP ID : journals/jcisd/ImadaONA11
  • Web of Science ID : WOS:000297275000002

エクスポート
BibTeX RIS