KMC 3: counting and manipulating k-mer statistics (2024)

Search for other works by this author on:

Article history

Abstract

1 Introduction

In many applications related to genome sequencing, e.g. de novo assembly, read correction, repeat detection and comparison of genomes, the first step is k-mer counting. This procedure consists in determining all unique k-symbol long strings (usually with counters) in the read collection.

From the conceptual point of view k-mer counting is quite simple task. Nevertheless, the problems appear when we deal with real data, which could be huge. There are many articles published in the recent years that discuss this problem, which shows that providing an efficient tool solving this task is far from trivial.

The obtained k-mer statistics are of course only a point of departure for following analyzes. In some of them various operations on sets of k-mers are necessary. We introduce a new version of KMC2 (Deorowicz et al., 2015), which is more memory frugal and much faster. We also introduce KMC tools for easy manipulation of sets produced by KMC. The usefulness of KMC tools is shown on a few literature case studies in which various utilities were replaced by operations from our package with significant gains in processing time and memory usage.

2 Materials and methods

KMC3 follows the same two-stage processing scheme as KMC2. In the first stage the reads are split into several hundred bins (disk files) according to the signatures (short m-symbol long substrings) of k-mers. The bins are then sorted one by one to remove duplicates in the second stage. A similar processing was used in several recently published algorithms for k-mer counting. Their first stages are similar to KMC2, but then the bins are handled in different ways, e.g. Gerbil (Erbert et al., 2017) employs hash tables, DSK2 (Rizk et al., 2013) uses multistage processing in a case of small disk space. Recently published, KCMBT (Mamun et al., 2016) applies burst tries for k-mer storage. Jellyfish (Marcais and Kingsford, 2011) utilizes thread-safe hash tables.

There are several main novelties in KMC3. Concerning the first stage, input files, especially in gzipped FASTQ format, are loaded faster due to better input/output (I/O) subsystem. Signatures are assigned to bins in an improved way, i.e. larger default signature length (nine instead of seven) is picked and larger part of input data is taken in the pre-processing stage in which the signatures are assigned to bins. These lead to better balance of bin sizes (at the cost of slightly larger total size of bins), which results in smaller main memory requirements and faster processing in the second stage. The most significant improvements are in the second stage. Both KMC (Deorowicz et al., 2013) and KMC2 used the least-significant-digit (LSD) radix sort. When the keys to sort are long (which happens when k > 32) the LSD radix sort requires unnecessarily many iterations over the data. Therefore, in KMC3 we implemented the fastest existing most-significant-digit radix sort (Kokot et al., 2016). We also improved the parallelization scheme of other routines (not directly related to sorting) at this stage.

The second part of the package consists of various tools for manipulation of sets containing k-mers. Figure 1 shows a general scheme of the package (complete description is given in the Supplementary Material). The filtering allows to extract from FASTQ files the reads satisfying some criteria, e.g. with sufficiently large number of k-mers occurrences. The family of transform operations allows to modify the KMC database, e.g. remove too frequent/rare k-mers, remove counters, build histogram. The family of simple operations is composed of several set operations involving more than one KMC database. For example, the user is able to intersect, union the databases. Finally, the complex operations allow to construct compound expressions taking as parameters KMC databases.

3 Results

We used six datasets for KMC3 evaluation. Table 1 shows the results for two representatives. The description of the datasets, the platform used for tests, the remaining results are given in the Supplementary Material. FASTQ files are almost always stored in compressed form. Thus, we provide the running times for both: uncompressed and gzipped FASTQ.

As we can observe for the Gallus gallus data, KMC3 is usually the fastest, especially for larger k. The times for hom*o sapiens 3, the largest of our dataset, are much longer. Nevertheless, KMC3 was able to complete in <100 min for typical input format for both examined k. It can be observed, that the improved I/O subsystem as well as the new sorting routine and better parallelization of the second stage gave substantial benefits comparing to KMC2. It is also worth noting that KMC3 even for the largest dataset used a reasonable amount of memory.

To evaluate KMC tools we picked three studies described recently in the literature. Below we briefly describe the goals of the studies and total gains in time and memory. The detailed results together with the scripts showing KMC tools usage are given in the Supplementary Material.

DIAMUND (Salzberg et al., 2014) is a novel approach for variant detection. It is dedicated to comparison of family trios or normal and diseased samples of the same individual. Instead of mapping the reads onto a reference genome, DIAMUND compares directly the raw reads. We followed this protocol for the Ashkenazim Jewish ancestry trio (Zook et al., 2016). DIAMUND needed 13 h to complete its work and used 107 GB RAM. As most of the stages can be made using KMC tools we replaced the original tools used in DIAMUND and reduced the processing time to 4 h (reducing memory usage to 12 GB RAM).

NIKS (Nordström et al., 2013) is another tool that uses raw sequencing reads for mutation identification taking into account mainly k-mer statistics. We replaced its stages related to k-mer counting and manipulation of k-mer databases by KMC tools operations. In a single stage it was necessary to use KMC API to prepare a short C ++ program to reproduce the format of intermediary data used in NIKS. The processing time for Oryza sativa dataset (83.3 GB input FASTQ) was reduced from ∼40 to 5 min in this case (RAM usage was reduced from 92 to 12 GB).

Finally, we made the same experiment as used in the GenomeTester4 article (Kaplinski et al., 2015), introducing a tool that is able to perform similar operations as KMC tools. The investigated problem was to find group-specific k-mers to identify bacteria. The processing time was reduced from 5 h to 15 min (RAM usage reduction from 75 to 12 GB).

4 Discussion

We proposed a new version of our k-mer counter. It is much faster (even a few times for large k) than its predecessor and faster than the existing competitors. The KMC tools offer a number of operations on k-mer databases that can be used in projects making use of k-mer statistics.

Funding

This work was supported by the Polish National Science Centre under the project DEC-2015/17/B/ST6/01890 and by Silesian University of Technology grant no. (BKM507/RAU2/2016). We used the infrastructure supported by POIG.02.03.01-24-099/13 grant: ‘GeCONiI–Upper Silesian Center for Computational Science and Engineering’.

Conflict of Interest: none declared.

References

© The Author 2017. Published by Oxford University Press. All rights reserved. For Permissions, please e-mail: journals.permissions@oup.com

Email alerts

Citing articles via

More from Oxford Academic