Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds

• Item type: SIG Technical Reports(1)
• 公開日: 2013-12-04
• タイトル: Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
• タイトル / 言語: en
• タイトル: Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者所属: Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者所属: Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者所属: Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
• 著者所属: Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者所属(英): en
• 著者所属(英): Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者所属(英): en
• 著者所属(英): Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者所属(英): en
• 著者所属(英): Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者名: Yang, Zhao; Morihiro, Hayashida; Jira, Jindalertudomdee; Hiroshi, Nagamochi; Tatsuya, Akutsu
• 著者名(英): Yang, Zhao; Morihiro, Hayashida; Jira, Jindalertudomdee; Hiroshi, Nagamochi; Tatsuya, Akutsu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Enumeration of chemical compounds plays a basic role in the design of drugs and the determination of chemical structures from mass spectrometry. Hence, it has been studied by mathematicians and computer scientists as well as chemists for quite a long time. In this technical report, we restrict enumerated structures to trees, and propose efficient algorithms, BfsSimEnum and BfsMulEnum for enumeration of tree-like chemical compounds without and with multiple bonds, respectively. Unlike many existing approaches, our methods iteratively add each atom to a balanced tree by breadth-first search order. In order to reduce large search space, we adjust some important concepts such as left-heavy, center-rooted and normal form to balanced trees. For evaluation of efficiency, we perform experiments for several instances, and compare our methods with existing methods. The results suggest that our proposed methods are exact and more efficient.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Enumeration of chemical compounds plays a basic role in the design of drugs and the determination of chemical structures from mass spectrometry. Hence, it has been studied by mathematicians and computer scientists as well as chemists for quite a long time. In this technical report, we restrict enumerated structures to trees, and propose efficient algorithms, BfsSimEnum and BfsMulEnum for enumeration of tree-like chemical compounds without and with multiple bonds, respectively. Unlike many existing approaches, our methods iteratively add each atom to a balanced tree by breadth-first search order. In order to reduce large search space, we adjust some important concepts such as left-heavy, center-rooted and normal form to balanced trees. For evaluation of efficiency, we perform experiments for several instances, and compare our methods with existing methods. The results suggest that our proposed methods are exact and more efficient.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12055912
• 書誌情報: 研究報告バイオ情報学（BIO）; 巻 2013-BIO-36, 号 15, p. 1-6, 発行日 2013-12-04
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会