ダウンロード数: 412
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s10910-010-9789-9.pdf | 452.24 kB | Adobe PDF | 見る/開く |
タイトル: | Efficient enumeration of stereoisomers of tree structured molecules using dynamic programming |
著者: | Imada, Tomoki Ota, Shunsuke Nagamochi, Hiroshi Akutsu, Tatsuya https://orcid.org/0000-0001-9763-797X (unconfirmed) |
著者名の別形: | 永持, 仁 |
キーワード: | Chemical enumeration Stereoisomers Tree structured molecules Dynamic programming |
発行日: | Apr-2011 |
出版者: | Springer Science+Business Media, LLC. |
誌名: | Journal of Mathematical Chemistry |
巻: | 49 |
号: | 4 |
開始ページ: | 910 |
終了ページ: | 970 |
抄録: | 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. |
著作権等: | The final publication is available at www.springerlink.com This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
URI: | http://hdl.handle.net/2433/139571 |
DOI(出版社版): | 10.1007/s10910-010-9789-9 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。