title: On optimizing distance-based similarity search for biological databases.
abstract: Similarity search leveraging distance-based index structures is increasingly being used for both multimedia and biological database applications. We consider distance-based indexing for three important biological data types, protein k-mers with the metric PAM model, DNA k-mers with Hamming distance and peptide fragmentation spectra with a pseudo-metric derived from cosine distance. To date, the primary driver of this research has been multimedia applications, where similarity functions are often Euclidean norms on high dimensional feature vectors. We develop results showing that the character of these biological workloads is different from multimedia workloads. In particular, they are not intrinsically very high dimensional, and deserving different optimization heuristics. Based on MVP-trees, we develop a pivot selection heuristic seeking centers and show it outperforms the most widely used corner seeking heuristic. Similarly, we develop a data partitioning approach sensitive to the actual data distribution in lieu of median splits.
authors.affiliation: Department of Computer Sciences, Center for Computational Biology and Bioinformatics, University of Texas at Austin, 1 University Station C0500, Austin, TX 78712-0233, USA. rmao@cs.utexas.edu
authors.forename: Rui
authors.initials: R
authors.lastname: Mao
authors.forename: Weijia
authors.initials: W
authors.lastname: Xu
authors.forename: Smriti
authors.initials: S
authors.lastname: Ramakrishnan
authors.forename: Glen
authors.initials: G
authors.lastname: Nuckolls
authors.forename: Daniel P
authors.initials: DP
authors.lastname: Miranker
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D003628:Database Management Systems; D030541:Databases, Genetic; D016247:Information Storage and Retrieval / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*; D017385:Sequence Homology; D014584:User-Computer Interface