Shared Nearest Neighbor Clustering in a Locality Sensitive Hashing Framework - CEA - Commissariat à l’énergie atomique et aux énergies alternatives Accéder directement au contenu
Article Dans Une Revue Journal of Computational Biology Année : 2018

Shared Nearest Neighbor Clustering in a Locality Sensitive Hashing Framework

Résumé

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.
Fichier principal
Vignette du fichier
kanj2017.pdf (173.5 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

cea-01765667 , version 1 (10-01-2019)

Identifiants

Citer

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⟩
153 Consultations
790 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More