Rxivist logo

KmerStream: Streaming algorithms for k-mer abundance estimation

By Páll Melsted, Bjarni V. Halldórsson

Posted 07 Apr 2014
bioRxiv DOI: 10.1101/003962 (published DOI: 10.1093/bioinformatics/btu713)

Motivation: Several applications in bioinformatics, such as genome assemblers and error corrections methods, rely on counting and keeping track of k-mers (substrings of length k). Histograms of k-mer frequencies can give valuable insight into the underlying distribution and indicate the error rate and genome size sampled in the sequencing experiment. Results: We present KmerStream, a streaming algorithm for computing statistics for high throughput sequencing data based on the frequency of k-mers. The algorithm runs in time linear in the size of the input and the space requirement are logarithmic in the size of the input. This very low space requirement allows us to deal with much larger datasets than previously presented algorithms. We derive a simple model that allows us to estimate the error rate of the sequencing experiment, as well as the genome size, using only the aggregate statistics reported by KmerStream and validate the accuracy on sequences from a PhiX control. As an application we show how KmerStream can be used to compute the error rate of a DNA sequencing experiment. We run KmerStream on a set of 2656 whole genome sequenced individuals and compare the error rate to quality values reported by the sequencing equipment. We discover that while the quality values alone are largely reliable as a predictor of error rate, there is considerable variability in the error rates between sequencing runs, even when accounting for reported quality values. Availability: The tool KmerStream is written in C++ and is released under a GPL license. It is freely available at https://github.com/pmelsted/KmerStream

Download data

  • Downloaded 1,343 times
  • Download rankings, all-time:
    • Site-wide: 5,755 out of 77,600
    • In bioinformatics: 1,075 out of 7,500
  • Year to date:
    • Site-wide: 53,737 out of 77,600
  • Since beginning of last month:
    • Site-wide: 37,224 out of 77,600

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)