Unknown

Dataset Information

0

CMash: fast, multi-resolution estimation of k-mer-based Jaccard and containment indices.


ABSTRACT:

Motivation

K-mer-based methods are used ubiquitously in the field of computational biology. However, determining the optimal value of k for a specific application often remains heuristic. Simply reconstructing a new k-mer set with another k-mer size is computationally expensive, especially in metagenomic analysis where datasets are large. Here, we introduce a hashing-based technique that leverages a kind of bottom-m sketch as well as a k-mer ternary search tree (KTST) to obtain k-mer-based similarity estimates for a range of k values. By truncating k-mers stored in a pre-built KTST with a large k=kmax value, we can simultaneously obtain k-mer-based estimates for all k values up to kmax. This truncation approach circumvents the reconstruction of new k-mer sets when changing k values, making analysis more time and space-efficient.

Results

We derived the theoretical expression of the bias factor due to truncation. And we showed that the biases are negligible in practice: when using a KTST to estimate the containment index between a RefSeq-based microbial reference database and simulated metagenome data for 10 values of k, the running time was close to 10× faster compared to a classic MinHash approach while using less than one-fifth the space to store the data structure.

Availability and implementation

A python implementation of this method, CMash, is available at https://github.com/dkoslicki/CMash. The reproduction of all experiments presented herein can be accessed via https://github.com/KoslickiLab/CMASH-reproducibles.

Supplementary information

Supplementary data are available at Bioinformatics online.

SUBMITTER: Liu S 

PROVIDER: S-EPMC9235470 | biostudies-literature |

REPOSITORIES: biostudies-literature

Similar Datasets

| S-EPMC6929325 | biostudies-literature
| S-EPMC10505501 | biostudies-literature
| S-EPMC6479077 | biostudies-literature
| S-EPMC6754423 | biostudies-literature
| S-EPMC7358456 | biostudies-literature
| S-EPMC5017348 | biostudies-literature
| S-EPMC4080738 | biostudies-literature
| S-EPMC3895138 | biostudies-literature
| S-EPMC6833257 | biostudies-literature
| S-EPMC9298075 | biostudies-literature