Skip to Main content Skip to Navigation
New interface
Journal articles

Shared Nearest Neighbor Clustering in a Locality Sensitive Hashing Framework

Abstract : We present a new algorithm to cluster high-dimensional sequence data and its application to the field of metagenomics, which aims at reconstructing individual genomes from a mixture of genomes sampled from an environmental site, without any prior knowledge of reference data (genomes) or the shape of clusters. Such problems typically cannot be solved directly with classical approaches seeking to estimate the density of clusters, for example, using the shared nearest neighbors (SNN) rule, due to the prohibitive size of contemporary sequence datasets. We explore here a new approach based on combining the SNN rule with the concept of locality sensitive hashing (LSH). The proposed method, called LSH-SNN, works by randomly splitting the input data into smaller-sized subsets (buckets) and employing the SNN rule on each of these buckets. Links can be created among neighbors sharing a sufficient number of elements, hence allowing clusters to be grown from linked elements. LSH-SNN can scale up to larger datasets consisting of millions of sequences, while achieving high accuracy across a variety of sample sizes and complexities.
Complete list of metadata

Cited literature [65 references]  Display  Hide  Download
Contributor : Léna Le Roy Connect in order to contact the contributor
Submitted on : Thursday, January 10, 2019 - 1:03:59 PM
Last modification on : Friday, February 18, 2022 - 3:21:55 AM


Files produced by the author(s)



Sawsan Kanj, Thomas Bruls, Stéphane Gazut. Shared Nearest Neighbor Clustering in a Locality Sensitive Hashing Framework. Journal of Computational Biology, 2018, 25 (2), pp.236 - 250. ⟨10.1089/cmb.2017.0113⟩. ⟨cea-01765667⟩



Record views


Files downloads