TY - GEN
T1 - Balanced multi-process parallel algorithm for chemical compound inference with given path frequencies
AU - Zhou, Jiayi
AU - Yu, Kun Ming
AU - Lin, Chun Yuan
AU - Shih, Kuei Chung
AU - Tang, Chuan Yi
PY - 2010
Y1 - 2010
N2 - To enumerate chemical compounds with given path frequencies is a fundamental procedure in Chemo- and Bio-informatics. The applications include structure determination, novel molecular development, etc. The problem complexity has been proven as NP-hard. Many methods have been proposed to solve this problem. However, most of them are heuristic algorithms. Fujiwara et al. propose a sequential branch-and-bound algorithm. Although it reaches all solutions and avoids exhaustive searching, the computation time still increases significantly when the number of atoms increases. Hence, in this paper, a parallel algorithm is presented for solving this problem. The experimental results showed that computation time was reduced even when more processes were launched. Moreover, the speed-up ratio for most of the test cases was satisfactory and, furthermore, it showed potential for use in drug design.
AB - To enumerate chemical compounds with given path frequencies is a fundamental procedure in Chemo- and Bio-informatics. The applications include structure determination, novel molecular development, etc. The problem complexity has been proven as NP-hard. Many methods have been proposed to solve this problem. However, most of them are heuristic algorithms. Fujiwara et al. propose a sequential branch-and-bound algorithm. Although it reaches all solutions and avoids exhaustive searching, the computation time still increases significantly when the number of atoms increases. Hence, in this paper, a parallel algorithm is presented for solving this problem. The experimental results showed that computation time was reduced even when more processes were launched. Moreover, the speed-up ratio for most of the test cases was satisfactory and, furthermore, it showed potential for use in drug design.
KW - Branch-and-bound algorithm
KW - Chemical compound inference
KW - Drug design
KW - Load-balancing
UR - https://www.scopus.com/pages/publications/79956279127
U2 - 10.1007/978-3-642-13136-3_18
DO - 10.1007/978-3-642-13136-3_18
M3 - 会议稿件
AN - SCOPUS:79956279127
SN - 3642131352
SN - 9783642131356
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 178
EP - 187
BT - Algorithms and Architectures for Parallel Processing - 10th International Conference, ICA3PP 2010, Workshops
T2 - 10th International Conference Algorithms and Architectures for Parallel Processing, ICA3PP 2010
Y2 - 21 May 2010 through 23 May 2010
ER -