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 metadatas

Cited literature [65 references]  Display  Hide  Download

https://hal-cea.archives-ouvertes.fr/cea-01765667
Contributor : Léna Le Roy <>
Submitted on : Thursday, January 10, 2019 - 1:03:59 PM
Last modification on : Monday, May 13, 2019 - 11:14:23 AM

File

kanj2017.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

118

Files downloads

121