Unknown

Dataset Information

0

Improving Bloom Filter Performance on Sequence Data Using k-mer Bloom Filters.


ABSTRACT: Using a sequence's k-mer content rather than the full sequence directly has enabled significant performance improvements in several sequencing applications, such as metagenomic species identification, estimation of transcript abundances, and alignment-free comparison of sequencing data. As k-mer sets often reach hundreds of millions of elements, traditional data structures are often impractical for k-mer set storage, and Bloom filters (BFs) and their variants are used instead. BFs reduce the memory footprint required to store millions of k-mers while allowing for fast set containment queries, at the cost of a low false positive rate (FPR). We show that, because k-mers are derived from sequencing reads, the information about k-mer overlap in the original sequence can be used to reduce the FPR up to 30 × with little or no additional memory and with set containment queries that are only 1.3 - 1.6 times slower. Alternatively, we can leverage k-mer overlap information to store k-mer sets in about half the space while maintaining the original FPR. We consider several variants of such k-mer Bloom filters (kBFs), derive theoretical upper bounds for their FPR, and discuss their range of applications and limitations.

SUBMITTER: Pellow D 

PROVIDER: S-EPMC5467106 | biostudies-literature | 2017 Jun

REPOSITORIES: biostudies-literature

altmetric image

Publications

Improving Bloom Filter Performance on Sequence Data Using k-mer Bloom Filters.

Pellow David D   Filippova Darya D   Kingsford Carl C  

Journal of computational biology : a journal of computational molecular cell biology 20161109 6


Using a sequence's k-mer content rather than the full sequence directly has enabled significant performance improvements in several sequencing applications, such as metagenomic species identification, estimation of transcript abundances, and alignment-free comparison of sequencing data. As k-mer sets often reach hundreds of millions of elements, traditional data structures are often impractical for k-mer set storage, and Bloom filters (BFs) and their variants are used instead. BFs reduce the mem  ...[more]

Similar Datasets

| S-EPMC2887045 | biostudies-literature
| S-EPMC4816029 | biostudies-literature
| S-EPMC5547447 | biostudies-other
| S-EPMC9710589 | biostudies-literature
| S-EPMC3974045 | biostudies-literature
| S-EPMC5411771 | biostudies-literature
| S-EPMC3166945 | biostudies-literature
| S-EPMC9994790 | biostudies-literature
| S-EPMC4832552 | biostudies-literature
| S-EPMC5791358 | biostudies-literature