Shared Nearest Neighbor Clustering in a Locality Sensitive Hashing Framework.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Metagenomics involves reconstructing individual genomes from environmental DNA mixtures.
• Classical clustering methods struggle with large-scale, high-dimensional sequence data.
• Existing approaches often require prior knowledge of reference genomes or cluster shapes.

Purpose of the Study:

• To introduce a scalable and accurate algorithm for clustering high-dimensional sequence data.
• To address the limitations of traditional methods in metagenomic applications.
• To enable genome reconstruction without prior reference data.

Main Methods:

• A novel algorithm combining Shared Nearest Neighbors (SNN) with Locality Sensitive Hashing (LSH) was developed.
• The LSH-SNN method partitions data into subsets (buckets) for SNN analysis.
• Clusters are grown by linking neighboring elements that share sufficient data points.

Main Results:

• LSH-SNN demonstrates scalability for datasets with millions of sequences.
• The algorithm achieves high accuracy across diverse sample sizes and complexities.
• Successful application in metagenomics for reconstructing individual genomes from mixed samples.

Conclusions:

• LSH-SNN offers a robust solution for clustering large, high-dimensional sequence data.
• The method overcomes limitations of classical approaches in metagenomics.
• This algorithm facilitates genome reconstruction without reliance on reference genomes.