Gerbil: a Fast and Memory-efficient -mer Counter with GPU-support

Background: A basic task in bioinformatics is the counting of -mers in genome sequences. Existing -mer counting tools are most often optimized for small  < 32 and suffer from excessive memory resource consumption or degrading performance for large . However, given the technology trend towards long reads of next-generation sequencers, support for large  becomes increasingly important.

Results: We present the open source -mer counting software that has been designed for the efficient counting of -mers for  ≥ 32. Our software is the result of an intensive process of algorithm engineering. It implements a two-step approach. In the first step, genome reads are loaded from disk and redistributed to temporary files. In a second step, the -mers of each temporary file are counted via a hash table approach. In addition to its basic functionality, can optionally use GPUs to accelerate the counting step. In a set of experiments with real-world genome data sets, we show that is able to efficiently support both small and large .

Conclusions: While 's performance is comparable to existing state-of-the-art open source -mer counting tools for small  < 32, it vastly outperforms its competitors for large , thereby enabling new applications which require large values of .