2026-07-21T23:46:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17048 2024-03-06T10:58:37Z ddc:004 open_access

Efficient Reconciliation of Genomic Datasets of High Similarity Shibuya, Yoshihiro Belazzougui, Djamal Kucherov, Gregory k-mers sketching Invertible Bloom Lookup Tables IBLT MinHash syncmers minimizers 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yoshihiro Shibuya and Djamal Belazzougui and Gregory Kucherov 2022 Is Part Of LIPIcs, Volume 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2022.14 urn:nbn:de:0030-drops-170481 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.14 eng https://creativecommons.org/licenses/by/4.0/legalcode