Speeding up chemical database searches using a proximity filter based on the logical exclusive or

Area of Science:

• Chemoinformatics
• Computational Chemistry
• Database Management

Background:

• Molecules in chemoinformatics databases are often represented by long binary fingerprint vectors.
• Searching these large databases for similar molecules can be computationally intensive.

Purpose of the Study:

• To develop a novel method for accelerating similarity searches in large chemoinformatics databases.
• To reduce the computational cost and time required for database queries.

Main Methods:

• Proposed storing a small XOR header vector with each molecular fingerprint.
• Utilized the XOR header to rapidly derive bounds on fingerprint vector intersections and unions.
• Developed probabilistic models to predict XOR header behavior and pruning efficiency.
• Validated the approach through experimental results on a large molecular dataset.

Main Results:

• The XOR header method allows for rapid estimation of similarity bounds (e.g., Tanimoto measure).
• Unfavorable bounds enable rapid discarding of molecules, significantly reducing search space.
• Experimental results show search speedups of 2-3 times over previous methods.
• For a Tanimoto threshold of 0.9, less than 10% of the database requires searching.

Conclusions:

• XOR headers provide an efficient mechanism for accelerating chemoinformatics database searches.
• This approach significantly enhances search performance by enabling early pruning of dissimilar molecules.
• The method offers substantial improvements in search speed and efficiency for large chemical datasets.