title: Tree and Hashing Data Structures to Speed up Chemical Searches: Analysis and Experiments.
abstract: In many large chemoinformatics database systems, molecules are represented by long binary fingerprint vectors whose components record the presence or absence of particular functional groups or combinatorial features. For a given query molecule, one is interested in retrieving all the molecules in the database with a similarity to the query above a certain threshold. Here we describe a method for speeding up chemical searches in these large databases of small molecules by combining previously developed tree and hashing data structures to prune the search space without any false negatives. More importantly, we provide a mathematical analysis that allows one to predict the level of pruning, and validate the quality of the predictions of the method through simulation experiments.
authors.affiliation: School of Information and Computer Sciences, Institute for Genomics and Bioinformatics, University of California, Irvine, Irvine, CA 92697-3435, USA.
authors.forename: Ramzi
authors.initials: R
authors.lastname: Nasr
authors.affiliation: Bioinformatics Research Center (BiRC), Aarhus University, CF Møllers Allé 8, DK-8000 Århus C, Denmark.
authors.forename: Thomas
authors.initials: T
authors.lastname: Kristensen
authors.affiliation: School of Information and Computer Sciences, Institute for Genomics and Bioinformatics, University of California, Irvine, Irvine, CA 92697-3435, USA. pfbaldi@ics.uci.edu.
authors.forename: Pierre
authors.initials: P
authors.lastname: Baldi
keywords: Computational chemistry; Drug design; Hashing data structures; Tree data structures