title: A fast, lock-free approach for efficient parallel counting of occurrences of k-mers.
abstract: BACKGROUND
  Counting the number of occurrences of every k-mer (substring of length k) in a long string is a central subproblem in many applications, including genome assembly, error correction of sequencing reads, fast multiple sequence alignment and repeat detection. Recently, the deep sequence coverage generated by next-generation sequencing technologies has caused the amount of sequence to be processed during a genome project to grow rapidly, and has rendered current k-mer counting tools too slow and memory intensive. At the same time, large multicore computers have become commonplace in research facilities allowing for a new parallel computational paradigm.
  
  
  RESULTS
  We propose a new k-mer counting algorithm and associated implementation, called Jellyfish, which is fast and memory efficient. It is based on a multithreaded, lock-free hash table optimized for counting k-mers up to 31 bases in length. Due to their flexibility, suffix arrays have been the data structure of choice for solving many string problems. For the task of k-mer counting, important in many biological applications, Jellyfish offers a much faster and more memory-efficient solution.
  
  
  BACKGROUND
  The Jellyfish software is written in C++ and is GPL licensed. It is available for download at http://www.cbcb.umd.edu/software/jellyfish.
authors.affiliation: Department of Computer Science, University of Maryland, College Park, MD 20742, USA. gmarcais@umd.edu
authors.forename: Guillaume
authors.initials: G
authors.lastname: Marçais
authors.forename: Carl
authors.initials: C
authors.lastname: Kingsford
mesh_terms: D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D016678:Genome; D006801:Humans; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software