2011年11月
Efficient Enumeration of Stereoisomers of Outerplanar Chemical Graphs Using Dynamic Programming
JOURNAL OF CHEMICAL INFORMATION AND MODELING
- ,
- ,
- ,
- 巻
- 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