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

  • Morihiro Hayashida
    Bioinformatics Center, Institute for Chemical Research, Kyoto University
  • Jira Jindalertudomdee
    Bioinformatics Center, Institute for Chemical Research, Kyoto University
  • Yang Zhao
    Bioinformatics Center, Institute for Chemical Research, Kyoto University
  • Tatsuya Akutsu
    Bioinformatics Center, Institute for Chemical Research, Kyoto University

Search this article

Description

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.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 2014 (23), 1-2, 2014-02-24

    Information Processing Society of Japan (IPSJ)

Details 詳細情報について

  • CRID
    1572261552743193088
  • NII Article ID
    110009673895
  • NII Book ID
    AN10505667
  • ISSN
    09196072
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top