khmer

khmer provides probabilistic k-mer counting and memory-efficient assembly graph representation to analyze and process DNA shotgun sequencing data from genomes, transcriptomes, metagenomes, and single-cell studies.

Key Features:

• Memory Efficiency: Uses a Count-Min Sketch probabilistic data structure for online updating and retrieval of k-mer counts with a markedly reduced memory footprint compared to exact structures such as hash tables, suffix arrays, or tries.
• Speed and Performance: Optimized for rapid generation of k-mer frequency distributions and efficient retrieval of individual k-mer counts, with benchmarking reported against Tallymer, Jellyfish, BFCounter, DSK, KMC, Turtle, and KAnalyze.
• Error Profiling and Data Normalization: Accounts for systematic overcounts inherent to Count-Min Sketches while enabling sequencing error profiling, k-mer abundance trimming, and digital normalization to mitigate false positives.
• Graph Representation for Assembly: Employs Bloom filter–based, memory-efficient graph representations to capture k-mer connectivity and enable de novo assembly storage using as little as 4 bits per k-mer.
• Metagenomic Partitioning: Uses graph partitioning of k-mer connectivity to divide assembly graphs into components, reducing maximum memory requirements for metagenome assembly by reported orders of magnitude (up to ~40-fold in reported examples).
• Multi-context Sequencing Support: Applicable to analysis of shotgun sequencing datasets from genomes, transcriptomes, metagenomes, and single-cell experiments.

Scientific Applications:

• De Novo Assembly: Enables memory- and time-efficient assembly of complex metagenomic and genomic datasets via compact k-mer graph representations and partitioning.
• Repeat Detection: Identifies repetitive sequences through k-mer abundance analysis.
• Sequencing Coverage Estimation: Estimates sequencing depth and coverage patterns across genomes and transcriptomes using k-mer frequency distributions.
• Error Profiling and Normalization: Profiles sequencing errors and performs k-mer abundance trimming and digital normalization to reduce error-related artifacts in downstream analyses.
• Metagenomic Component Separation: Partitions metagenomic assembly graphs into components to facilitate downstream assembly and reduce computational resources.

Methodology:

Implements probabilistic data structures—Count-Min Sketches for streaming k-mer counting and Bloom filters for memory-efficient assembly graph representation—together with k-mer abundance trimming, digital normalization, and sequencing error profiling.