Chemical Structure Searching in Chemical Compound Graph Databases

Abstract

In chemical informatics, the structure of chemical compound can be represented as graph with atoms as nodes and bonds as edges. Exact structural graph matching (automorphism), exact substructure graph matching (subgraph isomorphism) and graph similarity searching are important research areas of chemical informatics. In this paper, we develop the system for efficient exact graph matching and graph similarity searching using the edge code. The structural information of chemical graph is generated as the edge code. To improve the precision of exact graph matching, we use our novel edge code index structure to find the automorphic graph in the database. For similarity searching, we utilize the fuzzy query similarity graph matching based on the edge code to improve the computational speed. Finally, we conduct an extensive set of experiments on chemical compound database to demonstrate the efficiency of our approach for efficient exact graph matching and similarity searching.