Finding the nearest neighbors in biological databases using less distance computations.

Area of Science:

• Bioinformatics
• Computational Biology
• Data Science

Background:

• Biological applications frequently require similarity comparisons between large datasets like genomes and protein structures, which are computationally intensive.
• Efficiently identifying similar biological objects in massive databases is crucial for inferring functions and relationships.

Purpose of the Study:

• To present a novel technique for accelerating the k-nearest neighbor (k-nn) search.
• To significantly reduce the number of computationally expensive distance calculations required for similarity comparisons in large biological datasets.

Main Methods:

• The study introduces a speedup technique for k-nn search utilizing novel concepts of virtual pivots and partial pivots.
• The method dynamically locates virtual pivots based on the query to enhance pruning ability, thereby minimizing distance computations.
• Database preprocessing effort is comparable to or less than existing methods.

Main Results:

• The new method demonstrated a substantial speedup, using no more than 40% of the distance computations compared to the second-best method.
• Performance was evaluated on a database of 10,000 gene sequences, outperforming established k-nn search methods like M-Tree, OMNI, SA-Tree, and LAESA.
• The method's efficacy was shown on biological sequence datasets, including HIV-1 viral strain computational genotyping.

Conclusions:

• The proposed virtual and partial pivot-based k-nn search offers significant computational efficiency for biological similarity comparisons.
• This technique provides a practical solution for accelerating analyses involving large-scale biological data, such as genomic and proteomic studies.
• The method shows promise for applications like computational genotyping and functional inference from sequence data.