Accelerating Large-Scale Molecular Similarity Search through Exploiting High Performance Computing
Authors:
- 1 November 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 330-333
Abstract
Molecular similarity search is a simple but powerful chemoinformatics tool to rapidly find molecules that are structurally similar to a known reference compound from a large molecular database. A variety of indexing structures had been developed to improve the performance of similarity search over the large compound database. However, those algorithms often require a large computational cost to build indices and process queries, especially for a large-scale molecular dataset. We study the problem of accelerating similarity search using high performance computing (HPC) and design general algorithms to speed up existing indexing algorithms. We first propose a parallel algorithm based on data chunking, working for all indexing algorithms for similarity search. We theoretically analyze its computation cost and relationships between the speedup and number of data chunks. We further propose a parallel query algorithm for all graph-based indexing algorithms to accelerate their query processing in HPC. Both of our algorithms consistently offer a greater speedup than the baseline algorithm(s) when evaluated with different datasets and parameter settings.Keywords
This publication has 11 references indexed in Scilit:
- Metric Similarity Joins Using MapReduceIEEE Transactions on Knowledge and Data Engineering, 2016
- Chemical Structure Similarity Search for Ligand-based Virtual Screening: Methods and Computational ResourcesCurrent Drug Targets, 2016
- An Efficient Parallel Top-k Similarity Join for Massive Multidimensional Data Using SparkInternational Journal of Database Theory and Application, 2015
- Approximate nearest neighbor algorithm based on navigable small world graphsInformation Systems, 2014
- Speeding Up Chemical Searches Using the Inverted Index: The Convergence of Chemoinformatics and Text Search MethodsJournal of Chemical Information and Modeling, 2012
- ChEMBL: a large-scale bioactivity database for drug discoveryNucleic Acids Research, 2011
- Extended-Connectivity FingerprintsJournal of Chemical Information and Modeling, 2010
- Similarity-based virtual screening using 2D fingerprintsDrug Discovery Today, 2006
- Approximate nearest neighbors1998
- Satisfying general proximity / similarity queries with metric treesInformation Processing Letters, 1991