Speeding Up Chemical Database Searches Using a Proximity Filter Based on the Logical Exclusive OR.
Saved in:
| Title: | Speeding Up Chemical Database Searches Using a Proximity Filter Based on the Logical Exclusive OR. |
|---|---|
| Authors: | Pierre Baldi, Daniel S. Hirschberg, Ramzi J. Nasr |
| Source: | Journal of Chemical Information & Modeling. Jun2008, Vol. 48 Issue 7, p1367-1378. 12p. |
| Subjects: | Cheminformatics, Database searching, Molecular structure, Graph theory, Chemical structure, Physical & theoretical chemistry research |
| Abstract: | In many large chemoinformatics database systems, molecules are represented by long binary fingerprint vectors whose components record the presence or absence in the molecular graphs of particular functional groups or combinatorial features, such as labeled paths or labeled trees. To speed up database searches, we propose to store with each fingerprint a small header vector containing primarily the result of applying the logical exclusive OR (XOR) operator to the fingerprint vector after modulo wrapping to a smaller number of bits, such as 128 bits. From the XOR headers of two molecules, tight bounds on the intersection and union of their fingerprint vectors can be rapidly obtained, yielding tight bounds on derived similarity measures, such as the Tanimoto measure. During a database search, every time these bounds are unfavorable, the corresponding molecule can be rapidly discarded with no need for further inspection. We derive probabilistic models that allow us to estimate precisely the behavior of the XOR headers and the level of pruning under different conditions in terms of similarity threshold and fingerprint density. These theoretical results are corroborated by experimental results on a large set of molecules. For a Tanimoto threshold of 0.5 (respectively 0.9), this approach requires searching less than 50% (respectively 10%) of the database, leading to typical search speedups of 2 to 3 times over the previous state-of-the-art. [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!
