title: Speeding up chemical searches using the inverted index: the convergence of chemoinformatics and text search methods.
abstract: In ligand-based screening, retrosynthesis, and other chemoinformatics applications, one often seeks to search large databases of molecules in order to retrieve molecules that are similar to a given query. With the expanding size of molecular databases, the efficiency and scalability of data structures and algorithms for chemical searches are becoming increasingly important. Remarkably, both the chemoinformatics and information retrieval communities have converged on similar solutions whereby molecules or documents are represented by binary vectors, or fingerprints, indexing their substructures such as labeled paths for molecules and n-grams for text, with the same Jaccard-Tanimoto similarity measure. As a result, similarity search methods from one field can be adapted to the other. Here we adapt recent, state-of-the-art, inverted index methods from information retrieval to speed up similarity searches in chemoinformatics. Our results show a several-fold speed-up improvement over previous methods for both threshold searches and top-K searches. We also provide a mathematical analysis that allows one to predict the level of pruning achieved by the inverted index approach and validate the quality of these predictions through simulation experiments. All results can be replicated using data freely downloadable from http://cdb.ics.uci.edu/ .
authors.affiliation: Departments of Computer Science, University of California, Irvine, Irvine, California 92697-3435, United States.
authors.forename: Ramzi
authors.initials: R
authors.lastname: Nasr
authors.forename: Rares
authors.initials: R
authors.lastname: Vernica
authors.forename: Chen
authors.initials: C
authors.lastname: Li
authors.forename: Pierre
authors.initials: P
authors.lastname: Baldi
mesh_terms: D000465:Algorithms; D062126:Databases, Chemical; D057166:High-Throughput Screening Assays; D048088:Informatics / Q000379:methods / Q000706:statistics & numerical data*; D016013:Likelihood Functions; D015394:Molecular Structure; D054852:Small Molecule Libraries / Q000737:chemistry* / Q000145:classification; D014584:User-Computer Interface
chemical_list: D054852:Small Molecule Libraries