title: These are not the k-mers you are looking for: efficient online k-mer counting using a probabilistic data structure.
abstract: K-mer abundance analysis is widely used for many purposes in nucleotide sequence analysis, including data preprocessing for de novo assembly, repeat detection, and sequencing coverage estimation. We present the khmer software package for fast and memory efficient online counting of k-mers in sequencing data sets. Unlike previous methods based on data structures such as hash tables, suffix arrays, and trie structures, khmer relies entirely on a simple probabilistic data structure, a Count-Min Sketch. The Count-Min Sketch permits online updating and retrieval of k-mer counts in memory which is necessary to support online k-mer analysis algorithms. On sparse data sets this data structure is considerably more memory efficient than any exact data structure. In exchange, the use of a Count-Min Sketch introduces a systematic overcount for k-mers; moreover, only the counts, and not the k-mers, are stored. Here we analyze the speed, the memory usage, and the miscount rate of khmer for generating k-mer frequency distributions and retrieving k-mer counts for individual k-mers. We also compare the performance of khmer to several other k-mer counting packages, including Tallymer, Jellyfish, BFCounter, DSK, KMC, Turtle and KAnalyze. Finally, we examine the effectiveness of profiling sequencing error, k-mer abundance trimming, and digital normalization of reads in the context of high khmer false positive rates. khmer is implemented in C++ wrapped in a Python interface, offers a tested and robust API, and is freely available under the BSD license at github.com/ged-lab/khmer.
authors: Department of Computer Science and Engineering, Michigan State University, East Lansing, Michigan, United States of America.
authors: Qingpeng
authors: Q
authors: Zhang
authors: Department of Computer Science and Engineering, Michigan State University, East Lansing, Michigan, United States of America.
authors: Jason
authors: J
authors: Pell
authors: Department of Computer Science and Engineering, Michigan State University, East Lansing, Michigan, United States of America.
authors: Rosangela
authors: R
authors: Canino-Koning
authors: Department of Microbiology and Molecular Genetics, Michigan State University, East Lansing, Michigan, United States of America; Department of Plant, Soil, and Microbial Sciences, Michigan State University, East Lansing, Michigan, United States of America.
authors: Adina Chuang
authors: AC
authors: Howe
authors: Department of Computer Science and Engineering, Michigan State University, East Lansing, Michigan, United States of America; Department of Microbiology and Molecular Genetics, Michigan State University, East Lansing, Michigan, United States of America.
authors: C Titus
authors: CT
authors: Brown
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D006801:Humans; D009711:Nucleotides; D017422:Sequence Analysis, DNA; D012984:Software
chemical_list: D009711:Nucleotides