Application of kernel functions for accurate similarity search in large chemical databases
View/ Open
Issue Date
2010Author
Wang, Xiaohong
Huan, Luke
Smalter, Aaron Matthew
Lushington, Gerald H.
Publisher
BioMed Central
Type
Article
Article Version
Scholarly/refereed, publisher version
Rights
Copyright © 2010 Huan et al; licensee BioMed Central Ltd. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Metadata
Show full item recordAbstract
BackgroundSimilaritysearch in chemical structure databases is an important problem with many applications in chemical genomics, drug design, and efficient chemical probe screening among others. It is widely believed that structure based methods provide an efficient way to do the query. Recently various graph kernel functions have been designed to capture the intrinsic similarity of graphs. Though successful in constructing accurate predictive and classification models, graph kernel functions can not be applied to large chemical compound database due to the high computational complexity and the difficulties in indexing similarity search for large databases.
ResultsTo bridge graph kernel function and similarity search in chemical databases, we applied a novel kernel-based similarity measurement, developed in our team, to measure similarity of graph represented chemicals. In our method, we utilize a hash table to support new graph kernel function definition, efficient storage and fast search. We have applied our method, named G-hash, to large chemical databases. Our results show that the G-hash method achieves state-of-the-art performance for k-nearest neighbor (k-NN) classification. Moreover, the similarity measurement and the index structure is scalable to large chemical databases with smaller indexing size, and faster query processing time as compared to state-of-the-art indexing methods such as Daylight fingerprints, C-tree and GraphGrep.
ConclusionsEfficient similarity query processing method for large chemical databases is challenging since we need to balance running time efficiency and similarity search accuracy. Our previous similarity search method, G-hash, provides a new way to perform similarity search in chemical databases. Experimental study validates the utility of G-hash in chemical databases.
Collections
Citation
Wang, Xiaohong, Jun Huan, Aaron Smalter, and Gerald H. Lushington. "Application of Kernel Functions for Accurate Similarity Search in Large Chemical Databases." 2009 IEEE International Conference on Bioinformatics and Biomedicine (2009). http://dx.doi.org/10.1186/1471-2105-11-S3-S8
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.
Except where otherwise noted, this item's license is described as: Copyright © 2010 Huan et al; licensee BioMed Central Ltd. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.