Proceedings of the 2005 IEEE Computa- tional Systems Bioinformatics Conference, Stanford University
On optimizing distance-based similarity search for biological databases
作者:
R. Mao， W. J. Xu， S. Ramakrishnan， G. Nuckolls and D. P. Miranker
关键词:
Indexing； Multimedia databases； Bioinformatics； Indexes； Biological system modeling； Hamming distance； Peptides； Data structures； Information retrieval； Biology computing
摘要:
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.
在线下载