title: Turtle: identifying frequent k-mers with cache-efficient algorithms.
abstract: BACKGROUND
  Counting the frequencies of k-mers in read libraries is often a first step in the analysis of high-throughput sequencing data. Infrequent k-mers are assumed to be a result of sequencing errors. The frequent k-mers constitute a reduced but error-free representation of the experiment, which can inform read error correction or serve as the input to de novo assembly methods. Ideally, the memory requirement for counting should be linear in the number of frequent k-mers and not in the, typically much larger, total number of k-mers in the read library.
  
  
  RESULTS
  We present a novel method that balances time, space and accuracy requirements to efficiently extract frequent k-mers even for high-coverage libraries and large genomes such as human. Our method is designed to minimize cache misses in a cache-efficient manner by using a pattern-blocked Bloom filter to remove infrequent k-mers from consideration in combination with a novel sort-and-compact scheme, instead of a hash, for the actual counting. Although this increases theoretical complexity, the savings in cache misses reduce the empirical running times. A variant of method can resort to a counting Bloom filter for even larger savings in memory at the expense of false-negative rates in addition to the false-positive rates common to all Bloom filter-based approaches. A comparison with the state-of-the-art shows reduced memory requirements and running times.
  
  
  METHODS
  The tools are freely available for download at http://bioinformatics.rutgers.edu/Software/Turtle and http://figshare.com/articles/Turtle/791582.
authors.affiliation: Department of Computer Science, Department of Ecology, Evolution and Natural Resources, Institute of Marine and Coastal Sciences and BioMaPS Institute for Quantitative Biology, Rutgers University, New Brunswick, NJ 08901, USADepartment of Computer Science, Department of Ecology, Evolution and Natural Resources, Institute of Marine and Coastal Sciences and BioMaPS Institute for Quantitative Biology, Rutgers University, New Brunswick, NJ 08901, USADepartment of Computer Science, Department of Ecology, Evolution and Natural Resources, Institute of Marine and Coastal Sciences and BioMaPS Institute for Quantitative Biology, Rutgers University, New Brunswick, NJ 08901, USA.
authors.forename: Rajat Shuvro
authors.initials: RS
authors.lastname: Roy
authors.affiliation: Department of Computer Science, Department of Ecology, Evolution and Natural Resources, Institute of Marine and Coastal Sciences and BioMaPS Institute for Quantitative Biology, Rutgers University, New Brunswick, NJ 08901, USADepartment of Computer Science, Department of Ecology, Evolution and Natural Resources, Institute of Marine and Coastal Sciences and BioMaPS Institute for Quantitative Biology, Rutgers University, New Brunswick, NJ 08901, USA.
authors.forename: Debashish
authors.initials: D
authors.lastname: Bhattacharya
authors.affiliation: Department of Computer Science, Department of Ecology, Evolution and Natural Resources, Institute of Marine and Coastal Sciences and BioMaPS Institute for Quantitative Biology, Rutgers University, New Brunswick, NJ 08901, USADepartment of Computer Science, Department of Ecology, Evolution and Natural Resources, Institute of Marine and Coastal Sciences and BioMaPS Institute for Quantitative Biology, Rutgers University, New Brunswick, NJ 08901, USA.
authors.forename: Alexander
authors.initials: A
authors.lastname: Schliep
mesh_terms: D000465:Algorithms; D015894:Genome, Human; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software