Parallelization of Enumerating Tree-like Chemical Compounds by Breadth-first Search Order

• Item type: SIG Technical Reports(1)
• 公開日: 2014-02-24
• タイトル: Parallelization of Enumerating Tree-like Chemical Compounds by Breadth-first Search Order
• タイトル / 言語: en
• タイトル: Parallelization of Enumerating Tree-like Chemical Compounds by Breadth-first Search Order
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: ショートトーク
• 資源タイプ / 資源タイプ識別子: 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
• 著者所属: 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
• 著者所属(英): Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者名: Morihiro, Hayashida; Jira, Jindalertudomdee; Yang, Zhao; Tatsuya, Akutsu
• 著者名(英): Morihiro, Hayashida; Jira, Jindalertudomdee; Yang, Zhao; Tatsuya, Akutsu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Enumerating chemical compounds greatly assists designing drugs and determining chemical structures from mass spectrometry. In our previous study, we developed efficient algorithms, BfsSimEnum and BfsMulEnum for enumerating tree-like chemical compounds without and with multiple bonds, respectively. In this technical report, we develop a parallelized algorithm BfsEnumP by modifying BfsSimEnum in a simple manner to further reduce execution time. BfsSimEnum constructs a family tree in which each node denotes a molecular tree. BfsEnumP divides the family tree at some depth, and each subtree to be constructed is assigned to a processor. For evaluation, we perform experiments for several instances with varying the division depth and the number of processors, and show that it achieves about 80% parallelization efficiency.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Enumerating chemical compounds greatly assists designing drugs and determining chemical structures from mass spectrometry. In our previous study, we developed efficient algorithms, BfsSimEnum and BfsMulEnum for enumerating tree-like chemical compounds without and with multiple bonds, respectively. In this technical report, we develop a parallelized algorithm BfsEnumP by modifying BfsSimEnum in a simple manner to further reduce execution time. BfsSimEnum constructs a family tree in which each node denotes a molecular tree. BfsEnumP divides the family tree at some depth, and each subtree to be constructed is assigned to a processor. For evaluation, we perform experiments for several instances with varying the division depth and the number of processors, and show that it achieves about 80% parallelization efficiency.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 研究報告数理モデル化と問題解決（MPS）; 巻 2014-MPS-97, 号 23, p. 1-2, 発行日 2014-02-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会