SwiFT: an index structure for reduced graph descriptors in virtual screening and clustering

Area of Science:

• Computational chemistry
• Cheminformatics
• Bioinformatics

Background:

• Reduced graph descriptors, like feature trees, represent molecules for rapid similarity assessment.
• Existing algorithms compare feature trees by matching subtrees, creating alignments.
• Large datasets often contain numerous identical subtrees, posing computational challenges.

Purpose of the Study:

• To enhance the efficiency of feature tree comparison in large datasets.
• To develop a method for reusing partial comparison results on a global scale.
• To accelerate similarity calculations and identify duplicated molecular structures.

Main Methods:

• Indexing all unique subtrees within a dataset using a search tree.
• Computing similarity values for each subtree combination only once.
• Leveraging the index for parallel computation and duplicate detection.

Main Results:

• Achieved substantial reductions in runtime, up to 80%, for similarity calculations.
• Enabled efficient reuse of partial results across the entire feature tree dataset.
• The indexing search tree effectively identifies duplicated feature trees.

Conclusions:

• The proposed indexing method significantly optimizes feature tree comparison.
• This approach offers a scalable solution for large-scale molecular data analysis.
• The method is suitable for parallel processing environments and duplicate structure identification.