Enumerating Naphthalene Isomers of Tree-like Chemical Graphs

Fei He, Akiyoshi Hanai, Hiroshi Nagamochi, Tatsuya Akutsu

2016

Abstract

In this paper, we consider the problem of enumerating naphthalene isomers, where enumeration of isomers is important for drug design. A chemical graph G with no other cycles than naphthalene rings is called tree-like, and becomes a tree T possibly with multiple edges if we contract each naphthalene ring into a single virtual atom of valence 8. We call tree T the tree representation of G. There may be more than one tree-like chemical graphs whose tree representations equal to T, which are called naphthalene isomers of T. We present an efficient algorithm that enumerates all naphthalene isomers of a given tree representation. Our algorithm first counts the number of all the naphthalene isomers using dynamic programming, and then for each k, generates the k-th isomer by backtracking the counting computation. In computational experiment, we compare our method with MolGen, a state-of-the-art enumeration tool, and it is observed that our program enumerates the same number of naphthalene isomers within extremely shorter time, which proves that our algorithm is effectively built.

Paper Citation

in Harvard Style

He F., Hanai A., Nagamochi H. and Akutsu T. (2016). Enumerating Naphthalene Isomers of Tree-like Chemical Graphs . In Proceedings of the 9th International Joint Conference on Biomedical Engineering Systems and Technologies - Volume 3: BIOINFORMATICS, (BIOSTEC 2016) ISBN 978-989-758-170-0, pages 258-265. DOI: 10.5220/0005783902580265

in Bibtex Style

@conference{bioinformatics16,
author={Fei He and Akiyoshi Hanai and Hiroshi Nagamochi and Tatsuya Akutsu},
title={Enumerating Naphthalene Isomers of Tree-like Chemical Graphs},
booktitle={Proceedings of the 9th International Joint Conference on Biomedical Engineering Systems and Technologies - Volume 3: BIOINFORMATICS, (BIOSTEC 2016)},
year={2016},
pages={258-265},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005783902580265},
isbn={978-989-758-170-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 9th International Joint Conference on Biomedical Engineering Systems and Technologies - Volume 3: BIOINFORMATICS, (BIOSTEC 2016)
TI - Enumerating Naphthalene Isomers of Tree-like Chemical Graphs
SN - 978-989-758-170-0
AU - He F.
AU - Hanai A.
AU - Nagamochi H.
AU - Akutsu T.
PY - 2016
SP - 258
EP - 265
DO - 10.5220/0005783902580265