論文

査読有り
2011年4月

Efficient enumeration of stereoisomers of tree structured molecules using dynamic programming

JOURNAL OF MATHEMATICAL CHEMISTRY
  • Tomoki Imada
  • ,
  • Shunsuke Ota
  • ,
  • Hiroshi Nagamochi
  • ,
  • Tatsuya Akutsu

49
4
開始ページ
910
終了ページ
970
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1007/s10910-010-9789-9
出版者・発行元
SPRINGER

Nonredundant and exhaustive generation of 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 tree-like graphs because these compounds are most fundamental, and consider stereoisomers that can be generated by asymmetric carbon atoms and double bonds between two adjacent 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 subgraphs 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 the stereoisomers in O(n) space and in O(n) time per stereoisomer, where n is the number of atoms in a given structure. The source code of the program implementing the proposed algorithm is freely available for academic use upon request.

リンク情報
DOI
https://doi.org/10.1007/s10910-010-9789-9
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201102207659626377
CiNii Articles
http://ci.nii.ac.jp/naid/120003001339
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000289237500008&DestApp=WOS_CPL
ID情報
  • DOI : 10.1007/s10910-010-9789-9
  • ISSN : 0259-9791
  • J-Global ID : 201102207659626377
  • CiNii Articles ID : 120003001339
  • Web of Science ID : WOS:000289237500008

エクスポート
BibTeX RIS