## Improved Algorithms for Enumerating Tree-Like Chemical Graphs with Given Path Frequency

Yusuke Ishida[1] (yusukei@amp.i.kyoto-u.ac.jp)

Liang Zhao[1] (liang@amp.i.kyoto-u.ac.jp)

Hiroshi Nagamochi[1] (nag@amp.i.kyoto-u.ac.jp)

Tatsuya Akutsu[2] (takutsu@kuicr.kyoto-u.ac.jp)

[1] Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Yoshida, Kyoto 606-8501, Japan

[2] Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto 611-0011, Japan

### Abstract

This paper considers the problem of enumerating all non-isomorphic tree-like chemical graphs with given path frequency, where "tree-like" means that the graph can be viewed as a tree if multiple edges (i.e., edges with the same end points) and a benzene ring are treated as one edge and one vertex, respectively, and "path frequency" is a vector of the numbers of specified vertex-labeled paths that must be realized in every output. This and related problems have several potential applications such as classification of chemical compounds, structure determination using mass-spectrum and/or NMR and design of novel chemical compounds.

For this problem, several studies have been done. Recently, Fujiwara *et al*. (2008) showed two formulations and for each of them, they gave a branch-and-bound algorithm, which combined efficient enumeration of non-isomorphic trees with bounding operations based on the path frequency and the atom-atom bonds to avoid the generation of invalid trees. In this paper, based on their work and a result of Nagamochi (2006), we introduce two new bounding operations, the detachment-cut and the H-cut, to further reduce the size of the search space. We performed computational experiments to compare our proposed algorithms with those of Fujiwara *et al*. (2008) using some chemical compound data obtained from the KEGG LIGAND database (http://www.genome.jp/kegg/ligand.html). The results show that our proposed algorithms are much faster than their algorithms.

[ Full-text PDF |
Table of Contents ]

*Japanese Society for Bioinformatics*