Branch-and-bound algorithms for enumerating treelike chemical graphs with given path frequency using detachment-cut.
Computational methods of enumerating chemical graphs have attained great importance in chemoinformatics since they lead to a variety of useful applications including structure determination of novel chemical compounds. Recently, Fujiwara et al. have presented an efficient branch-and-bound algorithm for enumerating treelike chemical graphs with given path frequency. In this paper, we augment Fujiwara et al.'s algorithm by introducing a new bounding operation called detachment-cut to reduce further the search space in the branch-and-bound framework. Experimental results on much chemical compound data show that our proposed algorithm achieves better performance than Fujiwara et al.'s algorithm in computation time. A program that implements our algorithm can be used freely via Web server.
Ishida
Yusuke
Y
Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Yoshida, Kyoto 606-8501, Japan.
Kato
Yuki
Y
Zhao
Liang
L
Nagamochi
Hiroshi
H
Akutsu
Tatsuya
T
D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D003205:Computing Methodologies; D016208:Databases, Factual; D015394:Molecular Structure