Efficient reconciliation of genomic datasets of high similarity - CNRS - Centre national de la recherche scientifique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Efficient reconciliation of genomic datasets of high similarity

Résumé

We apply Invertible Bloom Lookup Tables (IBLTs) to the comparison of k-mer sets originated from large DNA sequence datasets. We show that for similar datasets, IBLTs provide a more space-efficient and, at the same time, more accurate method for estimating Jaccard similarity of underlying k-mer sets, compared to MinHash which is a go-to sketching technique for efficient pairwise similarity estimation. This is achieved by combining IBLTs with k-mer sampling based on syncmers, which constitute a context-independent alternative to minimizers and provide an unbiased estimator of Jaccard similarity. A key property of our method is that involved data structures require space proportional to the difference of k-mer sets and are independent of the size of sets themselves. As another application, we show how our ideas can be applied in order to efficiently compute (an approximation of) k-mers that differ between two datasets, still using space only proportional to their number. We experimentally illustrate our results on both simulated and real data (SARS-CoV-2 and Streptococcus Pneumoniae genomes).
Fichier principal
Vignette du fichier
aldiff.pdf (661.98 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-03867538 , version 1 (23-11-2022)

Identifiants

Citer

Yoshihiro Shibuya, Djamal Belazzougui, Gregory Kucherov. Efficient reconciliation of genomic datasets of high similarity. 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022), Sep 2022, Potsdam, Germany. ⟨10.4230/LIPIcs.WABI.2022.14⟩. ⟨hal-03867538⟩
17 Consultations
53 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More