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

Morihiro Hayashida, Jira Jindalertudomdee, Yang Zhao, Tatsuya Akutsu

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

この論文をさがす

CiNii Books

説明

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.