PaperlayerView exact revision on arXiv

Source-linked AI summary

KMC 2: Fast and resource-frugal $k$-mer counting

Sebastian Deorowicz, Marek Kokot, Szymon Grabowski, Agnieszka Debudaj-Grabysz

arXiv:1407.1507v1cs.DScs.CEq-bio.GN

TL;DR

Large sequencing datasets make k-mer counting a demanding problem because applications need fast frequency computation with moderate memory use. KMC 2 combines signatures, (k, x)-mers, and parallel disk-based processing to reduce resource demands and accelerate counting. It is reported as faster than competing counters, including about 20 minutes for 28-mers from a 44-fold human reads collection on a 6-core PC with an SSD.

  • Problem

    Efficient k-mer counting remains difficult at large scale because applications require high speed while limiting memory and disk demands.

  • Method

    KMC 2 uses carefully selected signatures, (k, x)-mers, and a highly parallel disk-based architecture to reduce binning, sorting, and I/O costs.

  • Results

    KMC 2 is reported as the fastest k-mer counter, about twice faster than Jellyfish 2 or KMC 1 on human datasets in SSD experiments.

  • Takeaways & Limitations

    KMC 2 provides fast k-mer counting with modest memory and disk requirements across a large range of datasets and test settings.

  • Takeaways & Limitations

    Minimizer-based partitioning can produce large A-rich bins and many short super k-mers, motivating KMC 2's signature design.

Abstract

from arXiv · show

Motivation: Building the histogram of occurrences of every $k$-symbol long substring of nucleotide data is a standard step in many bioinformatics applications, known under the name of $k$-mer counting. Its applications include developing de Bruijn graph genome assemblers, fast multiple sequence alignment and repeat detection. The tremendous amounts of NGS data require fast algorithms for $k$-mer counting, preferably using moderate amounts of memory. Results: We present a novel method for $k$-mer counting, on large datasets at least twice faster than the strongest competitors (Jellyfish~2, KMC~1), using about 12\,GB (or less) of RAM memory. Our disk-based method bears some resemblance to MSPKmerCounter, yet replacing the original minimizers with signatures (a carefully selected subset of all minimizers) and using $(k, x)$-mers allows to significantly reduce the I/O, and a highly parallel overall architecture allows to achieve unprecedented processing speeds. For example, KMC~2 allows to count the 28-mers of a human reads collection with 44-fold coverage (106\,GB of compressed size) in about 20 minutes, on a 6-core Intel i7 PC with an SSD. Availability: KMC~2 is freely available at http://sun.aei.polsl.pl/kmc. Contact: sebastian.deorowicz@polsl.pl

Motivation:

K-mer counting is widely used in bioinformatics, but efficient execution on large sequencing datasets requires both high speed and moderate memory. KMC 2 addresses these constraints with signatures, (k, x)-mers, and a parallel disk-based architecture.

  • K-mer counting computes frequencies of all k-long strings in sequencing reads for applications including de novo assembly, read correction, and repeat detection.
  • Existing efficient counters trade speed, memory, or disk usage: Jellyfish originally required more than 100 GB for human data, while DSK and KMC use disk-based partitioning.
  • KMC 2 reports several-times lower disk usage and usually about twice higher speed than KMC 1, with smaller memory consumption than its predecessor.
  • Canonical minimizers can create highly uneven bins and many single-k-mer super k-mers, increasing memory requirements and temporary disk usage.
  • Signatures replace pure minimizers with selected canonical minimizers that avoid problematic A-rich patterns, targeting smaller largest bins, balanced bin counts, and reduced total I/O.
  • (k, x)-mers reduce explicit sorting work by representing each super k-mer with fewer nonredundant units while preserving every contained k-mer.With x = 3, preliminary real-data experiments found about twice fewer (k, x)-mers than k-mers, nearly halving main-memory use.

3 RESULTS

KMC 2 was evaluated against competing k-mer counters across datasets, k values, and HDD/SSD configurations. It generally delivered strong speed and resource-efficiency results, with performance shaped by storage media, signatures, (k, x)-mers, k, and available memory.

  • Benchmark setup: KMC 2 was compared with Jellyfish 2, DSK, Turtle, MSPCounter, KAnalyze, and KMC 1 across k = 28 and 55 using HDD and SSD configurations.The evaluation used datasets of varying size, including two human datasets with large coverage.
  • Overall comparison: KMC 2 with standard memory was about twice faster than Jellyfish 2 or KMC 1 on the human datasets in SSD experiments.The speed gap diminished on HDD, where input/output was a bottleneck in several KMC 2 processing phases.
  • Input and storage effects: 25%–40% time reductions were observed when switching from HDD to SSD for KMC 2 on H. sapiens 2, with gzipped input also improving performance.The comparison varied both input format and storage medium on the largest dataset.
  • Signatures and (k, x)-mers: Signatures reduced average super k-mers per read by about 10–15 percent and sometimes more than halved the k-mer count in the largest disk bin.These reductions translated to lower RAM and temporary disk-space consumption compared with minimizers.
  • Signatures and (k, x)-mers: For x = 3, the number of strings to sort was more than halved, but the overall speedup was more moderate because of extra splitting and sorting longer strings.The comparison concerned (k, x)-mers versus plain k-mers.
  • Memory effects: Increasing memory from 16 GB to 40 GB produced only about 10% speedup, while reduced-memory runs were 5%–20% slower.More RAM enabled more sorter threads and allowed concurrent processing of bins; KMC 2 used 25 GB for (55, 0)-mers and 13 GB for (55, 3)-mers on H. sapiens 2.

4 CONCLUSION

KMC 2 combines modest resource requirements with high speed and stable performance across varied datasets and settings. It can process large human sequencing collections quickly on a multicore PC with an SSD.

  • KMC 2 is described as the fastest k-mer counter, with modest memory and disk requirements.Its speed is attributed to signatures, (k, x)-mers, and a highly parallel architecture.
  • KMC 2 worked stably across a large range of datasets and test settings.
  • 20 minutes suffices to count 28-mers from a 44-fold human reads collection of 106 GB compressed data on a 6-core Intel Core i7 PC with an SSD.
  • Memory-only execution is possible with enough RAM, but preliminary tests showed up to 5% speedup compared with an SSD.The memory-only mode may be attractive in datacenters using network HDDs with relatively low transfer.

Supplementary material for the paper

The supplementary material documents KMC 2 under its paper title and identifies its authors.

  • The supplementary material concerns KMC 2, a fast and resource-frugal k-mer counting program.
  • The title emphasizes KMC 2’s speed and resource frugality for k-mer counting.
  • The listed authors are Sebastian Deorowicz, Marek Kokot, Szymon Grabowski, and Agnieszka Debudaj-Grabysz.

1 KMC USAGE

The KMC command-line tool accepts FASTQ or related sequence inputs, configures memory and parallelism, and exposes filtering and counting options.

  • Command syntax and inputs: KMC accepts a single FASTQ file or a file listing FASTQ inputs and writes an output database file.Inputs may be gzipped or uncompressed.
  • Configuration options: Users can configure k-mer length, maximum RAM, signature length, input format, quality handling, counter bounds, and canonical-form transformation.
  • Parallel processing: KMC exposes separate controls for FASTQ readers, splitting, sorting, per-sorter threads, and total threads.These settings affect processing speed without changing output.
  • Usage examples: Usage examples show KMC counting k=27 reads with either a file list or a direct FASTQ input while allocating 24 GB of RAM.

2 API

The API provides classes for representing k-mers and accessing KMC databases through random-access or sequential-listing operations.

  • CKmerAPI: CKmerAPI represents k-mers and supports construction, copying, comparison, symbol access, and conversion between k-mers and ACGT strings.
  • CKMCFile: CKMCFile handles KMC databases and provides methods for opening, querying, listing, filtering, and retrieving database metadata.
  • Access modes: OpenForRA loads database files into memory for random access, whereas OpenForListing reads k-mers sequentially without loading the whole database.
  • Listing operations: Listing mode supports sequential iteration, restarting from the beginning, end-of-file detection, and reading each k-mer with its count.

3 EXAMPLE OF API USAGE

The dump application parses input and output parameters, opens a KMC database for listing, applies count bounds, and prints qualifying k-mers. Two dump variants differ mainly in counter-conversion speed, with the faster variant recommended for real applications.

  • Command-line parsing: The dump application accepts input and output file names and parses the -ci and -cx count-bound options.The command-line parser processes arguments beginning with a dash and extracts values following -ci and -cx.
  • Database access: A CKMCFile object opens the input database for listing, while SetMinCount and SetMaxCount constrain which k-mers are returned.The bounds must be no smaller than -ci and no greater than -cx, respectively; otherwise, nothing is listed.
  • Output format: Listed records contain the k-mer in natural representation followed by a tab and its integer or floating-point value.The output format is compatible with Quake and can be modified by changing the printing lines in Fig. 9.
  • Program variants: The dump program has two variants that perform essentially the same operation but print counters differently.The second variant replaces fprintf with a faster number-to-text conversion method.
  • Program variants: The faster counter-conversion variant should be used in real applications.The paper identifies this variant as preferable because its textual number conversion is faster than fprintf.

4 DATABASE FORMAT

KMC stores databases in paired .kmc pre and .kmc suf files with little-endian integers and explicit markers, headers, and packed k-mer records. The format supports locating prefix-indexed suffix ranges and interpreting occurrence or quality-aware counters.

  • 4 DATABASE FORMAT: KMC output uses pre files for k-mer-prefix information and suf files for k-mer suffixes with associated counters.The two extensions divide database metadata and records between prefix and suffix storage.
  • 4 DATABASE FORMAT: All integers in KMC output files use LSB, or little-endian, byte order.This byte order applies to the database’s integer fields.
  • 4.1 The .kmc pre file structure: The pre file begins and ends with KMCP markers, and its final position field points to the header.Readers verify both markers, read the header position eight bytes before the end, then locate the header using that position.
  • 4.1 The .kmc pre file structure: The header records minimum and maximum occurrence thresholds that determine whether k-mer data are written to the database.K-mers below the minimum or above the maximum are excluded.
  • 4.1 The .kmc pre file structure: The header also stores the total number of k-mers and reserves seven uint32 temporary fields unused in the current version.The total k-mer count is recorded as kmers, while tmp[7] is currently unused.

[map]

The map region indexes signatures to prefix-array locations using encoded DNA symbols. A worked example encodes ACGAC as 97 and uses that value to retrieve the related prefix-array identifier.

  • [map]: The map is an array of uint32 elements whose size is 4^signature_length + 1.Its entries identify the position of the proper-prefix array associated with each signature.
  • [map]: DNA symbols are encoded as A → 0, C → 1, G → 2, and T → 3 for signature indexing.This encoding converts signatures into integer positions in the map.
  • [map]: For signature ACGAC, the encoding yields 97, so the reader consults map position 97 to obtain the related prefix-array identifier.The example computes 97 from the encoded symbols’ positional values.

[prefixes]

The prefixes region stores arrays that map signature-and-prefix combinations to contiguous records in the suf file. The example then narrows the relevant range and binary-searches the target suffix.

  • [prefixes]: The prefixes region contains multiple uint64 prefix arrays, each with 4^lut_length elements and a trailing guard element.The arrays are typically numbered in the hundreds.
  • [prefixes]: For a given signature, an entry at prefix position x points to the corresponding record in the suf file.The next entry determines the end of the record range, using the following position minus one.
  • [prefixes]: For ATACGACAAATG with signature ACGAC, the prefix-array start is computed as 4 + 97 · 4^lut_length · 8.The factors represent the marker, signature index, array size, and eight-byte uint64 elements.
  • [prefixes]: With lut_length = 4, the prefix ATAC encodes as 49 and identifies the first matching suf-file record.The example uses the prefix entry associated with signature ACGAC.
  • [prefixes]: If the first and next prefix entries are 1523 and 1685, the matching records occupy positions 1523 through 1684.The suffix GACAAATG can then be located by binary search within that range.
  • [prefixes]: The suf file stores packed k-mer symbols and counters, with counters represented as one-to-four-byte integers or four-byte floats.The k-mer suffix is stored in (kmer_length)/4 bytes, followed by the counter field.

5 EXPERIMENTAL RESULTS

The experiments compare KMC 2 with several k-mer counters across multiple FASTQ datasets, k values, compression settings, and storage configurations. Competitor-specific parameters and resource limits were explicitly set for each tool.

  • Experimental setup: The test machine used a 6-core Intel i7 CPU, 64 GB RAM, paired 3 TB HDDs in RAID 0, and a 1 TB SSD.Buffered transfer rates were reported as 355 MB/s for the HDD array and 510 MB/s for the SSD.
  • Datasets: The evaluation used several decompressed FASTQ datasets, including fv.fastq, gg.fastq, mb.fastq, hs1.fastq, and hs2.fastq.Input files were downloaded from DDBJ, 1000 Genomes, or ENA sources and decompressed before testing.
  • Competitor configurations: Jellyfish was tested for k=28 and k=55 with expected k-mer counts set about 10% above the number reported by KMC.The command lines used 12 threads and dataset-specific hash-table sizes.
  • Competitor configurations: KAnalyze was evaluated only at k=28 because version 0.9.5 does not support counting k-mers for k > 32.Six threads were allocated to both its k-mer and split steps.
  • Competitor configurations: DSK used its default 6 GB RAM limit and excluded k-mers occurring fewer than 2 times, while MSPKmerCounter used minimizer length 10 and 1000 bins.scTurtle used 11 threads and an expected k-mer count set about 10% above KMC’s exact value.

6 AUTOMATIC SETTING OF PARAMETERS IN KMC

KMC 2 automatically allocates threads across input reading, splitting, bin sorting, and per-sorter sorting. The allocation depends on available cores, input compression and size, and second-stage memory requirements.

  • Automatic resource allocation: KMC 2’s automatic parameter setting allocates available resources across FASTQ readers, splitters, sorters, and sorting threads.The mechanism is intended to use CPU cores and memory across the two processing stages.
  • Configuration limits: The automatic allocation is necessarily suboptimal because the best thread counts depend on compression methods, disk speeds, and other factors.The experiments nevertheless report that the mechanism performs reasonably well, and users can specify settings manually.
  • First stage: For plain-text input, KMC 2 uses one FASTQ reader; for compressed input, readers match large-file count up to half the available cores.A large file is defined as exceeding 5% of the largest input file’s size.
  • Second stage: After reader assignment, remaining cores become splitting threads, while second-stage sorter threads are calculated as ⌊M2/B10⌋.M2 is available second-stage memory and B10 is the size of the bin larger than 10% of bins.
  • Second stage: Sorting threads are divided among sorters by the available core count, with some sorters receiving one additional thread when division is uneven.The example assigns 10 threads across 7 sorters as three sorters with 2 threads and four with 1.
Loading 1407.1507v1…