title: Branch-and-bound algorithms for enumerating treelike chemical graphs with given path frequency using detachment-cut.
abstract: 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.
authors.affiliation: Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Yoshida, Kyoto 606-8501, Japan.
authors.forename: Yusuke
authors.initials: Y
authors.lastname: Ishida
authors.forename: Yuki
authors.initials: Y
authors.lastname: Kato
authors.forename: Liang
authors.initials: L
authors.lastname: Zhao
authors.forename: Hiroshi
authors.initials: H
authors.lastname: Nagamochi
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D003205:Computing Methodologies; D016208:Databases, Factual; D015394:Molecular Structure