Bounds and Algorithms for Fast Exact Searches of Chemical Fingerprints in Linear and Sublinear Time.
Saved in:
| Title: | Bounds and Algorithms for Fast Exact Searches of Chemical Fingerprints in Linear and Sublinear Time. |
|---|---|
| Authors: | S. Joshua Swamidass1, Pierre Baldi1 |
| Source: | Journal of Chemical Information & Modeling. Mar2007, Vol. 47 Issue 2, p302-317. 16p. |
| Subjects: | Algorithms, Molecules, Database searching, QUERY (Information retrieval system), Databases, Mathematical formulas |
| Abstract: | Chemical fingerprints are used to represent chemical molecules by recording the presence or absence, or by counting the number of occurrences, of particular features or substructures, such as labeled paths in the 2D graph of bonds, of the corresponding molecule. These fingerprint vectors are used to search large databases of small molecules, currently containing millions of entries, using various similarity measures, such as the Tanimoto or Tversky's measures and their variants. Here, we derive simple bounds on these similarity measures and show how these bounds can be used to considerably reduce the subset of molecules that need to be searched. We consider both the case of single-molecule and multiple-molecule queries, as well as queries based on fixed similarity thresholds or aimed at retrieving the top Khits. We study the speedup as a function of query size and distribution, fingerprint length, similarity threshold, and database size Dand derive analytical formulas that are in excellent agreement with empirical values. The theoretical considerations and experiments show that this approach can provide linear speedups of one or more orders of magnitude in the case of searches with a fixed threshold, and achieve sublinear speedups in the range of O(D0.6) for the top Khits in current large databases. This pruning approach yields subsecond search times across the 5 million compounds in the ChemDB database, without any loss of accuracy. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Chemical Information & Modeling is the property of American Chemical Society and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
