Source-linked AI summary
KMC 3: counting and manipulating k-mer statistics
Marek Kokot, Maciej Długosz, Sebastian Deorowicz
TL;DR
Efficient k-mer counting is difficult on huge sequencing datasets, and downstream analyses also require operations on k-mer sets. KMC3 improves KMC2’s speed and memory use, while KMC tools manipulate k-mer databases and substantially accelerate several real workflows.
Problem
Huge sequencing datasets make efficient k-mer counting nontrivial, while subsequent analyses require operations on k-mer sets.
Method
KMC3 improves KMC2’s two-stage k-mer counting pipeline, and KMC tools provide filtering, transformation, and set operations on k-mer databases.
Results
KMC3 was usually fastest in dataset tests, while KMC tools reduced DIAMUND, NIKS, and GenomeTester4 workflows’ time and memory requirements.
Takeaways & Limitations
KMC3 and KMC tools support faster, lower-memory processing of k-mer-based workflows and provide operations applicable to several literature case studies.
Takeaways & Limitations
GenomeTester4 supports only FASTQ input and k below 33, while Jellyfish supports only FASTQ input.
Abstract
from arXiv · showhide
Summary: Counting all k-mers in a given dataset is a standard procedure in many bioinformatics applications. We introduce KMC3, a significant improvement of the former KMC2 algorithm together with KMC tools for manipulating k-mer databases. Usefulness of the tools is shown on a few real problems. Availability: Program is freely available at http://sun.aei.polsl.pl/REFRESH/kmc. Contact: sebastian.deorowicz@polsl.pl
1 Introduction
K-mer counting is a foundational step in genome-sequencing applications, but huge real datasets make efficient counting nontrivial. KMC3 addresses this challenge while adding tools for manipulating the resulting k-mer sets.
- K-mer counting determines all unique k-mer strings in read collections and supports applications including de novo assembly, read correction, repeat detection, and genome comparison.
- Huge real datasets make efficient k-mer counting far from trivial despite its conceptual simplicity.
- KMC3 improves KMC2 with lower memory usage and higher speed, while KMC tools manipulate k-mer databases.
- KMC tools replace operations in literature case studies with significant gains in processing time and memory usage.
2 Methods
KMC3 retains KMC2’s two-stage binning and sorting scheme but improves I/O, bin assignment, sorting, and parallelization. KMC tools then filter, transform, and combine k-mer databases.
- KMC3 splits reads into bins by k-mer signatures, then sorts each bin to remove duplicates.
- KMC3 accelerates gzipped FASTQ loading and assigns signatures to bins more efficiently, reducing memory requirements.
- The second stage replaces radix sort with a new algorithm and improves parallelization of other routines.
- KMC tools filter reads, transform databases, and perform simple or complex set operations such as intersection and union.
- The comparison reports execution time, disk, and RAM usage, generally using 12 threads; KCMBT used 8 threads because of high memory consumption.
3 Results
Across six datasets and three literature case studies, KMC3 and KMC tools generally reduced runtime and memory use. KMC3 was usually fastest, while tool-based replacements produced large workflow-level savings.
- The evaluation used six datasets, with running times reported for both uncompressed and gzipped FASTQ input.
- KMC3 was usually fastest on G. gallus data, especially for larger k, and completed the largest H. sapiens 3 dataset in under 100 minutes for both examined k values.
- KMC3’s improved I/O, sorting routine, and second-stage parallelization provided substantial benefits over KMC2 while using reasonable memory on the largest dataset.
- Replacing DIAMUND’s original tools reduced processing time from 13 hours to 4 hours and RAM usage from 107GB to 12GB.
- Replacing NIKS stages reduced processing time from approximately 40 minutes to 5 minutes and RAM usage from 92GB to 12GB.
- The GenomeTester4 case study’s processing time fell from 5 hours to 15 minutes, while RAM usage fell from 75GB to 12GB.
4 Discussion
KMC3 is presented as a faster successor to KMC2 and existing competitors, while KMC tools provide operations for projects using k-mer statistics.
- KMC3 is reported to be much faster than KMC2, by up to a few times for large k, and faster than existing competitors.
- KMC tools provide multiple operations on k-mer databases for projects that use k-mer statistics.
Supplementary material
The supplementary material identifies Marek Kokot, Maciej D lugosz, and Sebastian Deorowicz.
- Marek Kokot is listed among the authors.
- Maciej D lugosz is listed among the authors.
- Sebastian Deorowicz is listed among the authors.
1 Examined programs
The experiments compare multiple k-mer counting programs using specified commands, datasets, k-mer sizes, thread counts, and memory or disk settings.
- Examined programs: The compared programs are run with explicit command-line parameters for k-mer size, threads, input, output, and filtering.The supplied commands include program-specific options such as -kmer-size, -nb-cores, -t, -k, -i, and -w.
- Examined programs: KCMBT is run only at k-mer size 28 because its maximum supported k-mer size is 32.
- Running parameters: The Xeon settings generally use 12 threads, whereas the Opteron settings use 16 threads.The supplied commands and parameter description specify these platform-specific thread counts.
2 Environment
The experiments use two multicore systems: an Intel Xeon workstation and an AMD Opteron server, with different processors and storage configurations.
- Xeon-based workstation: The Intel Xeon workstation has two Xeon E5-2670 CPUs with 12 cores per CPU at 2.3 GHz.
- Xeon-based workstation: The Xeon workstation uses a 1 TB Samsung 850 EVO SSD and two 6 TB Seagate Enterprise NAS HDDs in RAID0.
- Opteron-based server: The AMD Opteron server has four Opteron 6320 CPUs with 8 cores per CPU at 2.8 GHz.
- Opteron-based server: The Opteron server uses five 1 TB Toshiba MG03SCA100 HDDs in RAID5.
3 k-mer counting
The evaluation uses six sequencing datasets and compares k-mer counting tools under compressed and uncompressed input conditions, with filtering and multicore execution settings defined.
- Datasets and running parameters: Six datasets are used for KMC3 evaluation, with representative results in Table 1 and remaining results in supplementary material.The datasets include F. vesca, G. gallus, M. balbisiana, and three H. sapiens datasets.
- Datasets and running parameters: Sequencing-error-derived rare k-mers are filtered by removing single-appearance k-mers in the reported subsection.Omitting this filtering usually changes running time and memory usage by less than 10 percent.
- Datasets and running parameters: The experiments report both uncompressed FASTQ time and gzipped FASTQ time, with gz-Time identified as more important.
4 KMC tools
KMC tools are evaluated as replacements for existing utilities in three k-mer analysis problems: DIAMUND, NIKS, and GenomeTester4. The replacements support direct database operations and yield substantial time or memory gains in the reported case studies.
- Evaluation problems: KMC tools were evaluated on de novo mutation detection, comparison of related WGS samples, and identification of bacteria-group-specific k-mers.The case studies correspond to DIAMUND, NIKS, and GenomeTester4, respectively.
- DIAMUND: DIAMUND compares family-member sequencing reads directly rather than aligning them to a reference genome, and KMC tools replaced its initial processing steps.The replacement included k-mer counting, set filtering, and read filtering; GenomeTester4 could not complete the pipeline because it lacked read filtering.
- NIKS: NIKS was improved by replacing k-mer counting, occurrence histograms, and sample-specific k-mer computation with KMC3 and KMC tools operations.The modified workflow required two executions for one unique-k-mer step, but remained much faster than the original approach.
- GenomeTester4: KMC tools construct bacteria-group-specific k-mers by combining counting, sorting, intersection, and compound database operations.The resulting pipeline reproduces the target set using supported operations, despite lacking a direct difference-from-union operation.