Improving Bloom Filter Performance on Sequence Data Using k -mer Bloom Filters
Authors:
Open Access
- 1 June 2017
- journal article
- research article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 24 (6) , 547-557
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.Keywords
This publication has 21 references indexed in Scilit:
- BLESS: Bloom filter-based error correction solution for high-throughput sequencing readsBioinformatics, 2014
- The difficulty of protein structure alignment under the RMSDAlgorithms for Molecular Biology, 2013
- Space-efficient and exact de Bruijn graph representation based on a Bloom filterAlgorithms for Molecular Biology, 2013
- Scaling metagenome sequence assembly with probabilistic de Bruijn graphsProceedings of the National Academy of Sciences, 2012
- A fast, lock-free approach for efficient parallel counting of occurrences of k-mersBioinformatics, 2011
- Classification of DNA sequences using Bloom filtersBioinformatics, 2010
- Velvet: Algorithms for de novo short read assembly using de Bruijn graphsGenome Research, 2008
- Using Bloom Filters for Large Scale Gene Sequence Analysis in HaskellLecture Notes in Computer Science, 2008
- Network Applications of Bloom Filters: A SurveyInternet Mathematics, 2004
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970