Development of a Chemical Structure Comparison Method for Integrated Analysis of Chemical and Genomic Information in the Metabolic Pathways

Cellular functions result from intricate networks of molecular interactions, which involve not only
proteins and nucleic acids but also small chemical compounds. Here we present an efficient algorithm for
comparing two chemical structures of compounds, where the chemical structure is treated as a graph
consisting of atoms as nodes and covalent bonds as edges. On the basis of the concept of functional
groups, 68 atom types (node types) are defined for carbon, nitrogen, oxygen, and other atomic species
with different environments, which has enabled detection of biochemically meaningful features. Maximal
common subgraphs of two graphs can be found by searching for maximal cliques in the association graph,
and we have introduced heuristics to accelerate the clique finding and to detect optimal local matches
(simply connected common subgraphs). Our procedure was applied to the comparison and clustering of
9383 compounds, mostly metabolic compounds, in the KEGG/LIGAND database. The largest clusters of
similar compounds were related to carbohydrates, and the clusters corresponded well to the categorization
of pathways as represented by the KEGG pathway map numbers. When each pathway map was examined
in more detail, finer clusters could be identified corresponding to subpathways or pathway modules containing
continuous sets of reaction steps. Furthermore, it was found that the pathway modules identified by similar
compound structures sometimes overlap with the pathway modules identified by genomic contexts, namely,
by operon structures of enzyme genes.