2-AIN-506 a 2-AIN-252: Seminár z bioinformatiky (2) a (4)
Leto 2015
Abstrakt

Qingpeng Zhang, Jason Pell, Rosangela Canino-Koning, Adina Chuang Howe, C. Titus Brown. These are not the k-mers you are looking for: efficient online k-mer countingusing a probabilistic data structure. PLoS One, 9(7):e101271. 2014.

Download preprint: not available

Download from publisher: not available PubMed

Related web page: not available

Bibliography entry: BibTeX

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.