A survey of k-mer methods and applications in bioinformatics

“BLAT[65], BLAST[68], BLASTX[64,282], DIAMOND [283], MMSeqs2[284], PAUDA[285], RAPSearch2 [286], USEARCH & UBLAST [287] Databases K-mer databases provide k-mer sequences that are present or absent in each species. kmerDB.com[171], nullomers. org[162] C. Moeckel et al. reference database of potential contaminants (Fig.”

“[249] BBMap[250], Bowtie2[251, 252], BWA[253 – 255], iMOKA [256], MiniMap2[71] Taxonomic Classification In sequence composition-based methods, the frequency and distribution of k-mers in metagenomic data are analyzed to assess genome similarity across various taxonomic ranks.”

“In de novo genome assemblers such as SPAdes [75] and multiple others [76], a common approach is to first divide sequencing reads into k-mers and use each unique k-mer to represent a node in a De Brujin Graph [77].”

“BLAT[65], BLAST[68], BLASTX[64,282], DIAMOND [283], MMSeqs2[284], PAUDA[285], RAPSearch2 [286], USEARCH & UBLAST [287] Databases K-mer databases provide k-mer sequences that are present or absent in each species. kmerDB.com[171], nullomers. org[162] C. Moeckel et al. reference database of potential…”

“Recently, k-mer-based alignment algorithms have been utilized in detecting and filtering out contamination by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis…”

“Allpaths-LG[239], Bifrost [240], Canu[241], Cortex [242], ELBA[243], KAT[223], MEGAHIT[244], Merqury [46], QUAST-LG[245], SKESA [246], SPAdes[75], TandemQUAST[247], TandemMapper[248] Sequence Comparison Alignment-free methods are increasingly used for DNA and protein sequence comparison since they…”

“Allpaths-LG[239], Bifrost [240], Canu[241], Cortex [242], ELBA[243], KAT[223], MEGAHIT[244], Merqury [46], QUAST-LG[245], SKESA [246], SPAdes[75], TandemQUAST[247], TandemMapper[248] Sequence Comparison Alignment-free methods are increasingly used for DNA and protein sequence comparison since they…”

“Notable examples include Kraken2 [136], KrakenUniq [19], YACHT [137], and Kaiju [138], which assign reads to taxa without alignment based on approximate matches to a reference database of genomic or proteomic sequences.”

“BLAT[65], BLAST[68], BLASTX[64,282], DIAMOND [283], MMSeqs2[284], PAUDA[285], RAPSearch2 [286], USEARCH & UBLAST [287] Databases K-mer databases provide k-mer sequences that are present or absent in each species. kmerDB.com[171], nullomers. org[162] C. Moeckel et al. reference database of potential contaminants (Fig.”

“…contamination by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis.jl [211], Kmerator[212], Kounta[213], Krust[214], Meryl[46],…”

“Furthermore, k-mer-based approaches, such as metaSPades, prove valuable for reconstructing individual genomes from metagenomic datasets [140].”

“Bio-informatic tools such as Jellyfish [8], KMC3 [45], Meryl [46], REIN-DEER [47], and Squeakr [48] leverage optimized data structures and algorithms and are commonly written in low-level programming languages to process large-scale genomic datasets and accurately determine k-mer abundance…”

“Recently, k-mer-based alignment algorithms have been utilized in detecting and filtering out contamination by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis…”

“Currently, minimizers are used to accelerate aligners such as Minimap2 [71] and assist algorithms such as Mash [72] in estimating the similarity between genomes.”

“Additionally, to understand the functional potential of metagenomic data, the distribution of k-mers associated with functional genes or metabolic pathways can be analyzed [134,135].”

“K-mers prove effective in capturing and predicting information about protein folding patterns [153], secondary structure elements [153], and tertiary structures [154].”

“Long-read sequencing technologies such as those developed by Pacific Biosciences (PacBio) and Oxford Nanopore provide long reads, which, unlike short-reads, are able to span repeated elements or repetitive regions in de novo genome assembly and structural variant calling [93].”

“BLAT[65], BLAST[68], BLASTX[64,282], DIAMOND [283], MMSeqs2[284], PAUDA[285], RAPSearch2 [286], USEARCH & UBLAST [287] Databases K-mer databases provide k-mer sequences that are present or absent in each species. kmerDB.com[171], nullomers. org[162] C. Moeckel et al. reference database of potential contaminants (Fig.”

“Notable examples include Kraken2 [136], KrakenUniq [19], YACHT [137], and Kaiju [138], which assign reads to taxa without alignment based on approximate matches to a reference database of genomic or proteomic sequences.”

“CRISPR-Cas9 (Clustered Regularly Interspaced Short Palindromic Repeats) enables precise and efficient genome editing, but encounters various analytical challenges such as understanding off-target effects and improving delivery efficiency [104,105].”

“GenomeScope[221], GenomeTester4[222], KAnalyze[207], KAT[223], KHMer[210] KmerGenie [224], KmerStream[225], ntCard[226], Squeakr[48] Sequence Indexing K-mer searches serve as effective proxies for both exact and approximate sequence searches in unassembled datasets.”

“BLAT[65], BLAST[68], BLASTX[64,282], DIAMOND [283], MMSeqs2[284], PAUDA[285], RAPSearch2 [286], USEARCH & UBLAST [287] Databases K-mer databases provide k-mer sequences that are present or absent in each species. kmerDB.com[171], nullomers. org[162] C. Moeckel et al. reference database of potential contaminants (Fig.”

“K-mer-based approaches in clinical metagenomics hold the potential for rapid diagnosis and monitoring of infectious diseases [141].”

“Allpaths-LG[239], Bifrost [240], Canu[241], Cortex [242], ELBA[243], KAT[223], MEGAHIT[244], Merqury [46], QUAST-LG[245], SKESA [246], SPAdes[75], TandemQUAST[247], TandemMapper[248] Sequence Comparison Alignment-free methods are increasingly used for DNA and protein sequence comparison since they…”

“One caveat of these methods is that they suffer from significantly higher error rates, necessitating novel methods of error correction [94 – 96].”

“[249] BBMap[250], Bowtie2[251, 252], BWA[253 – 255], iMOKA [256], MiniMap2[71] Taxonomic Classification In sequence composition-based methods, the frequency and distribution of k-mers in metagenomic data are analyzed to assess genome similarity across various taxonomic ranks.”

“Reference-based genome assembly can be utilized when a high quality reference genome is available [73].”

“In recent years, the field of genomics has undergone a significant transformation due to advances in sequencing technologies and the generation of both large and diverse datasets [1,2].”

“In recent years, the field of genomics has undergone a significant transformation due to advances in sequencing technologies and the generation of both large and diverse datasets [1,2].”

“For example, in de novo genome assembly, shorter k-mer lengths may reduce the quality of the resulting contigs, whereas longer k-mers have a higher chance of including errors [32].”

“Bio-informatic tools such as Jellyfish [8], KMC3 [45], Meryl [46], REIN-DEER [47], and Squeakr [48] leverage optimized data structures and algorithms and are commonly written in low-level programming languages to process large-scale genomic datasets and accurately determine k-mer abundance…”

“Allpaths-LG[239], Bifrost [240], Canu[241], Cortex [242], ELBA[243], KAT[223], MEGAHIT[244], Merqury [46], QUAST-LG[245], SKESA [246], SPAdes[75], TandemQUAST[247], TandemMapper[248] Sequence Comparison Alignment-free methods are increasingly used for DNA and protein sequence comparison since they…”

“Tools include RaGOO [74], which utilizes Minimap2 [71] alignments to a closely related reference genome with a k-mer size of 19 base pairs to cluster, order, and orient genome assembly contigs into pseudomolecules.”

“In large-scale prokaryote and virus projects, k-mer frequency-based tools like VirFinder are used to identify viral sequences in mixed metagenomic datasets containing both viral and host contigs [18].”

“Allpaths-LG[239], Bifrost [240], Canu[241], Cortex [242], ELBA[243], KAT[223], MEGAHIT[244], Merqury [46], QUAST-LG[245], SKESA [246], SPAdes[75], TandemQUAST[247], TandemMapper[248] Sequence Comparison Alignment-free methods are increasingly used for DNA and protein sequence comparison since they…”

“Importantly, Salmon, the successor of Sailfish [61], corrects for fragment GC-content bias to improve the accuracy of abundance estimates [59].”

“[257,258] Table 2 ( continued ) Application Description Tools (reference) [272], Taxonomer[273], TETRA[274], VirFinder[18], WGSQuikr[275]”

“The advancements have enabled the efficient acquisition of vast amounts of genomic information within a short timeframe [3].”

“[ 249] AAF[276], FSWM[277], PhyloPythia[278], Skmer [279], Slope-SpaM[280], SlopeTree[281] Protein Sequence”

“Lastly, Rcorrector is a k-mer-based method that relies on De Brujin graphs for correcting random sequencing errors in Illumina RNA-seq reads specifically [92].”

“Allpaths-LG[239], Bifrost [240], Canu[241], Cortex [242], ELBA[243], KAT[223], MEGAHIT[244], Merqury [46], QUAST-LG[245], SKESA [246], SPAdes[75], TandemQUAST[247], TandemMapper[248] Sequence Comparison Alignment-free methods are increasingly used for DNA and protein sequence comparison since they…”

“CRISPR-Cas9 (Clustered Regularly Interspaced Short Palindromic Repeats) enables precise and efficient genome editing, but encounters various analytical challenges such as understanding off-target effects and improving delivery efficiency [104,105].”

“2B) [68], k-mers can serve as effective minimizers to reduce memory and computational requirements for genomic data analysis (Table 1) [69].”

“To address this issue, some methods using gapped k-mers as features have been introduced [13,35].”

“2F) [19].”

“BLAT[65], BLAST[68], BLASTX[64,282], DIAMOND [283], MMSeqs2[284], PAUDA[285], RAPSearch2 [286], USEARCH & UBLAST [287] Databases K-mer databases provide k-mer sequences that are present or absent in each species. kmerDB.com[171], nullomers. org[162] C. Moeckel et al. reference database of potential…”

“[257,258] Table 2 ( continued ) Application Description Tools (reference) [272], Taxonomer[273], TETRA[274], VirFinder[18], WGSQuikr[275]”

“One caveat of these methods is that they suffer from significantly higher error rates, necessitating novel methods of error correction [94 – 96].”

“2C) [78 – 81].”

“…a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis.jl [211], Kmerator[212], Kounta[213], Krust[214], Meryl[46], MSPKmerCounter[215], REINDEER[47], RNA-Skim [60],…”

“One primary application of k-mers in comparative genomics is constructing phylogenetic trees by quantifying the genetic distance between species based on k-mer frequencies [114 – 118].”

“[257,258] Table 2 ( continued ) Application Description Tools (reference) [272], Taxonomer[273], TETRA[274], VirFinder[18], WGSQuikr[275]”

“In genome assembly, pangenome graphs, which model direct relationships between all genomes in the analysis, can be utilized to capture genetic diversity and understand genetic variations across different populations and species [82].”

“However, due to the exponential growth of the k-mer space, this probability drops to 0.01 at k = 19 [34].”

“Recently, k-mer-based alignment algorithms have been utilized in detecting and filtering out contamination by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis…”

“In terms of the first peak, k-mer spectrum-based algorithms have been developed to identify and remove sequencing read errors based on the infrequency of these k-mers [52 – 54].”

“Algorithms such as Pangenome-based Genome Inference or PanGenie use haplotype-resolved pangenome references and k-mer counts from short-read sequencing data to analyze genetic variation [83].”

“K-mer-based algorithms are widely utilized across genomic and proteomic applications and offer several advantages as fundamental units for analyses [6,7].”

“These methods enable comparative analysis of k-mer occurrences and distributions across genomes, facilitating the identification of conserved regions, gene families, regulatory motifs, and genomic rear-rangements to better understand evolutionary relationships [51, 111 – 113].”

“Interestingly, the tool Lighter fully avoids k-mer counting and relies instead on a pair of Bloom filters [88], while Karect [89], SAMDUDE [90], and CARE [91] utilize alignment-based approaches.”

“Previous reviews have focused on several of the research areas covered in this review, including sequence alignment [194,195], genome assembly [196], indexing and querying large datasets [197], and metagenomics-based methods and pipelines [6,198].”

“…[45], KmerAnalysis.jl [211], Kmerator[212], Kounta[213], Krust[214], Meryl[46], MSPKmerCounter[215], REINDEER[47], RNA-Skim [60], Salmon[59], SEEKR [134], SeqKit[216], Seqtrie [217], Squeakr[48], SWAPCounter[36], Tallymer [218], Turtle[219], VLmer [220] Frequency Analysis K-mer spectra can be used…”

“The development of machine learning models for predicting antimicrobial resistance faces challenges stemming from the high-dimensional and strong correlations of k-mer-based representations [20, 143, 144].”

“Allpaths-LG[239], Bifrost [240], Canu[241], Cortex [242], ELBA[243], KAT[223], MEGAHIT[244], Merqury [46], QUAST-LG[245], SKESA [246], SPAdes[75], TandemQUAST[247], TandemMapper[248] Sequence Comparison Alignment-free methods are increasingly used for DNA and protein sequence comparison since they…”

“[257,258] Table 2 ( continued ) Application Description Tools (reference) [272], Taxonomer[273], TETRA[274], VirFinder[18], WGSQuikr[275]”

“Conventional analytical approaches have struggled with the unprecedented scale and complexity of genomic datasets [4,5], necessitating the development of efficient algorithms for extracting relevant information.”

“K-mers can serve as valuable clinical biomarkers for detecting pathogens [17 – 19], antimicrobial resistance [17, 20, 21], and human diseases [16, 22 – 24].”

“…been utilized in detecting and filtering out contamination by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis.jl [211], Kmerator[212],…”

“Previous reviews have focused on several of the research areas covered in this review, including sequence alignment [194,195], genome assembly [196], indexing and querying large datasets [197], and metagenomics-based methods and pipelines [6,198].”

“Recent clinical investigations highlight the potential of peptide-based drugs in cancer therapy, emphasizing advantages such as their small size, specificity, efficacy across a broad spectrum of cancers, potentially selective cytotoxicity, and cost-effectiveness [188,189].”

“COBS[49], DiscoverY[227], HowDeSBT[228], KmerGO [229], Kmerind[230], Mantis [231], MetaGraph[232], PAC [233], RecoverY[234], SBT [235], SeqOthello[236], SSHash[237], VarGeno[238] Genome Assembly In de novo genome assembly, sequencing reads undergo fragmentation into k-mers, and their overlaps are…”

“For a detailed comparison, readers can also refer to a number of publications evaluating the strengths of individual approaches [101 – 103].”

“The development of machine learning models for predicting antimicrobial resistance faces challenges stemming from the high-dimensional and strong correlations of k-mer-based representations [20, 143, 144].”

“[249] BBMap[250], Bowtie2[251, 252], BWA[253 – 255], iMOKA [256], MiniMap2[71] Taxonomic Classification In sequence composition-based methods, the frequency and distribution of k-mers in metagenomic data are analyzed to assess genome similarity across various taxonomic ranks.”

“Other algorithms for short-read error correction include the k-mer spectrum-based error correctors Musket [52] and BLESS [53], which utilize both k-mer counting and a Bloom filter.”

“[ 249] AAF[276], FSWM[277], PhyloPythia[278], Skmer [279], Slope-SpaM[280], SlopeTree[281] Protein Sequence”

“Previous reviews have focused on several of the research areas covered in this review, including sequence alignment [194,195], genome assembly [196], indexing and querying large datasets [197], and metagenomics-based methods and pipelines [6,198].”

“Additional sketch-based methods that utilize k-mers in comparative genomics include Bindash 1.0 [122] and 2.0 [123], Dashing 1.0 [124] and 2.0 [125], NIQKI [126], SuperSampler [127], and fmh-funprofiler [128] (Table 2).”

“COBS[49], DiscoverY[227], HowDeSBT[228], KmerGO [229], Kmerind[230], Mantis [231], MetaGraph[232], PAC [233], RecoverY[234], SBT [235], SeqOthello[236], SSHash[237], VarGeno[238] Genome Assembly In de novo genome assembly, sequencing reads undergo fragmentation into k-mers, and their overlaps are…”

“K-mers can serve as valuable clinical biomarkers for detecting pathogens [17 – 19], antimicrobial resistance [17, 20, 21], and human diseases [16, 22 – 24].”

“Previous reviews have focused on several of the research areas covered in this review, including sequence alignment [194,195], genome assembly [196], indexing and querying large datasets [197], and metagenomics-based methods and pipelines [6,198].”

“Additionally, k-mer-based genome binning techniques, such as Phages from Metagenomics Binning (PHAMB), facilitate the extraction and categorization of thousands of viral genomes from bulk metagenomics datasets [139].”

“1B) [159, 162, 163].”

“Squeakr uses a counting quotient filter, providing memory efficiency, faster processing for larger k-mers, and also the option to obtain approximate counts at a much lower computational cost for applications where exact counts are not required [48].”

“For a detailed comparison, readers can also refer to a number of publications evaluating the strengths of individual approaches [101 – 103].”

“2A) [9, 10, 51, 55].”

“…HowDeSBT[228], KmerGO [229], Kmerind[230], Mantis [231], MetaGraph[232], PAC [233], RecoverY[234], SBT [235], SeqOthello[236], SSHash[237], VarGeno[238] Genome Assembly In de novo genome assembly, sequencing reads undergo fragmentation into k-mers, and their overlaps are employed to…”

“Short-read error correction algorithms include RECKONER [85,86] and RACER [87], which correct substitution errors, are dedicated to Illumina reads, and rely on k-mer counting.”

“Recent phylogenetic analyses have led to discoveries like the novel picorna-like viral sequences found in gut metagenomes [119,120].”

“Other tools include COBS, an inverted index based on Bloom filters [49], and MetaProFi, which utilizes k-mers to profile and query protein and nucleotide sequence data based on k-mer signatures [50].”

“For example, k-mer-based technologies like Redk-mer and BoostMEC analyze k-mer distributions to identify unique target sites with a low likelihood of off-target effects [106,107].”

“The utilization of k-mers in metaproteomics has even led to the identification of virion-associated protein annotations in “ viral dark matter ” genomic sequences [152].”

“Determining the abundance of taxonomic communities within diverse environments has important implications for agriculture, wild-life conservation, and healthcare improvements [129].”

“Bio-informatic tools such as Jellyfish [8], KMC3 [45], Meryl [46], REIN-DEER [47], and Squeakr [48] leverage optimized data structures and algorithms and are commonly written in low-level programming languages to process large-scale genomic datasets and accurately determine k-mer abundance…”

“GenomeScope[221], GenomeTester4[222], KAnalyze[207], KAT[223], KHMer[210] KmerGenie [224], KmerStream[225], ntCard[226], Squeakr[48] Sequence Indexing K-mer searches serve as effective proxies for both exact and approximate sequence searches in unassembled datasets.”

“GenomeScope[221], GenomeTester4[222], KAnalyze[207], KAT[223], KHMer[210] KmerGenie [224], KmerStream[225], ntCard[226], Squeakr[48] Sequence Indexing K-mer searches serve as effective proxies for both exact and approximate sequence searches in unassembled datasets.”

“…and filtering out contamination by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis.jl [211], Kmerator[212], Kounta[213], Krust[214],…”

“Recently, k-mer-based alignment algorithms have been utilized in detecting and filtering out contamination by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis…”

“BLAT[65], BLAST[68], BLASTX[64,282], DIAMOND [283], MMSeqs2[284], PAUDA[285], RAPSearch2 [286], USEARCH & UBLAST [287] Databases K-mer databases provide k-mer sequences that are present or absent in each species. kmerDB.com[171], nullomers. org[162] C. Moeckel et al. reference database of potential contaminants (Fig.”

“The selection of the minimizer k-mer is done through a deterministic procedure; traditionally, the smallest k-mer in lexico-graphical ordering is chosen, but more recently, other alternatives such as ordering based on universal hitting sets have also been proposed [70].”

“K-mer-based methods for profiling taxa consist of three steps: first, k-mer profiles are compared to reference datasets, the individual sequences are then labeled, and lastly, the abundance of microbial taxa in large-scale metagenomic datasets is estimated [118, 131, 132].”

“K-mer-based methods for profiling taxa consist of three steps: first, k-mer profiles are compared to reference datasets, the individual sequences are then labeled, and lastly, the abundance of microbial taxa in large-scale metagenomic datasets is estimated [118, 131, 132].”

“[ 249] AAF[276], FSWM[277], PhyloPythia[278], Skmer [279], Slope-SpaM[280], SlopeTree[281] Protein Sequence”

“Additional sketch-based methods that utilize k-mers in comparative genomics include Bindash 1.0 [122] and 2.0 [123], Dashing 1.0 [124] and 2.0 [125], NIQKI [126], SuperSampler [127], and fmh-funprofiler [128] (Table 2).”

“Similar to metagenomics, k-mers aid in identifying proteins and understanding the functional potential of microbial communities [149].”

“Conventional analytical approaches have struggled with the unprecedented scale and complexity of genomic datasets [4,5], necessitating the development of efficient algorithms for extracting relevant information.”

“[249] BBMap[250], Bowtie2[251, 252], BWA[253 – 255], iMOKA [256], MiniMap2[71] Taxonomic Classification In sequence composition-based methods, the frequency and distribution of k-mers in metagenomic data are analyzed to assess genome similarity across various taxonomic ranks.”

“2D) [66,67].”

“2D) [119].”

“[249] BBMap[250], Bowtie2[251, 252], BWA[253 – 255], iMOKA [256], MiniMap2[71] Taxonomic Classification In sequence composition-based methods, the frequency and distribution of k-mers in metagenomic data are analyzed to assess genome similarity across various taxonomic ranks.”

“COBS[49], DiscoverY[227], HowDeSBT[228], KmerGO [229], Kmerind[230], Mantis [231], MetaGraph[232], PAC [233], RecoverY[234], SBT [235], SeqOthello[236], SSHash[237], VarGeno[238] Genome Assembly In de novo genome assembly, sequencing reads undergo fragmentation into k-mers, and their overlaps are…”

“Recently, k-mer-based alignment algorithms have been utilized in detecting and filtering out contamination by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis…”

“Acquisti et al. challenged this idea and suggested that the mutational dynamics of the genome, namely the hypermutability of CpG dinucleotides in vertebrates, likely account for the emergence of certain short sequence motifs as nullomers (k = 11 bp) [174].”

“To address this issue, some methods using gapped k-mers as features have been introduced [13,35].”

“…[209], KHMer[210], KMC3 [45], KmerAnalysis.jl [211], Kmerator[212], Kounta[213], Krust[214], Meryl[46], MSPKmerCounter[215], REINDEER[47], RNA-Skim [60], Salmon[59], SEEKR [134], SeqKit[216], Seqtrie [217], Squeakr[48], SWAPCounter[36], Tallymer [218], Turtle[219], VLmer [220] Frequency Analysis…”

“In addition, Pinho et al. defined minimal absent words (MAWs) as absent sequences that lose the property of being absent from a genome (or sequence space by extension) if a character is removed from either end (Table 1) [162,165].”

“Moreover, k-mers can have intrinsic biological significance, and their distribution and frequency can provide insights into genomic characteristics such as repetitive elements, functional regions, genomic variation, and DNA damage and repair mechanisms [8 – 16].”

“…Canu[241], Cortex [242], ELBA[243], KAT[223], MEGAHIT[244], Merqury [46], QUAST-LG[245], SKESA [246], SPAdes[75], TandemQUAST[247], TandemMapper[248] Sequence Comparison Alignment-free methods are increasingly used for DNA and protein sequence comparison since they are much faster than…”

“5 GC-content was shown to influence the prevalence of specific k-mers, leading to decreased sequence entropy and SSC [56].”

“…by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis.jl [211], Kmerator[212], Kounta[213], Krust[214], Meryl[46], MSPKmerCounter[215],…”

“GenomeScope[221], GenomeTester4[222], KAnalyze[207], KAT[223], KHMer[210] KmerGenie [224], KmerStream[225], ntCard[226], Squeakr[48] Sequence Indexing K-mer searches serve as effective proxies for both exact and approximate sequence searches in unassembled datasets.”

“K-mers can serve as valuable clinical biomarkers for detecting pathogens [17 – 19], antimicrobial resistance [17, 20, 21], and human diseases [16, 22 – 24].”

“The development of machine learning models for predicting antimicrobial resistance faces challenges stemming from the high-dimensional and strong correlations of k-mer-based representations [20, 143, 144].”

“MAWs have been proposed as potential tools for drug discovery, design, and delivery as they may have specific binding affinities and interactions with other molecules [162, 166 – 169].”

“…of MAWs termed minimal relative absent words (RAWs) that are derived from a pathogen genome, but absent in its host, to analyze distinctions among Ebola virus sequences associated with the outbreak, sequences from other Ebola virus species, historical outbreak sequences, and the human genome [160].”

“1B) [159, 162, 163].”

“3C) [181 – 183].”

“[257,258] Table 2 ( continued ) Application Description Tools (reference) [272], Taxonomer[273], TETRA[274], VirFinder[18], WGSQuikr[275]”

“Metaproteomic datasets contain a vast array of protein sequences from diverse and unlabeled organisms, posing significant challenges for accurate identification and functional interpretation [147,148].”

“Previous reviews have focused on several of the research areas covered in this review, including sequence alignment [194,195], genome assembly [196], indexing and querying large datasets [197], and metagenomics-based methods and pipelines [6,198].”

“To enhance the interpretability of genomic signatures in k-mer-based predictive models, Jaillard et al. introduced an adaptive cluster lasso strategy, which identified sparse, meaningful, and interpretable genomic signatures and improved clinical utility [145].”

“In response to these issues, multiple hybrid approaches based on k-mers were proposed, utilizing long reads for scaffolding and short Illumina reads for correcting errors [97 – 100].”

“In response to these issues, multiple hybrid approaches based on k-mers were proposed, utilizing long reads for scaffolding and short Illumina reads for correcting errors [97 – 100].”

“[ 249] AAF[276], FSWM[277], PhyloPythia[278], Skmer [279], Slope-SpaM[280], SlopeTree[281] Protein Sequence”

“COBS[49], DiscoverY[227], HowDeSBT[228], KmerGO [229], Kmerind[230], Mantis [231], MetaGraph[232], PAC [233], RecoverY[234], SBT [235], SeqOthello[236], SSHash[237], VarGeno[238] Genome Assembly In de novo genome assembly, sequencing reads undergo fragmentation into k-mers, and their overlaps are…”

“By efficiently characterizing genetic material with k-mer-based approaches, diverse taxonomic groups can be identified and profiled [130].”

“In terms of the first peak, k-mer spectrum-based algorithms have been developed to identify and remove sequencing read errors based on the infrequency of these k-mers [52 – 54].”

“MAWs have been proposed as potential tools for drug discovery, design, and delivery as they may have specific binding affinities and interactions with other molecules [162, 166 – 169].”

“One primary application of k-mers in comparative genomics is constructing phylogenetic trees by quantifying the genetic distance between species based on k-mer frequencies [114 – 118].”

“Patel et al. found that rare five-mer peptides induced stronger cellular responses than common sequences [186].”

“[ 249] AAF[276], FSWM[277], PhyloPythia[278], Skmer [279], Slope-SpaM[280], SlopeTree[281] Protein Sequence”

“…observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45], KmerAnalysis.jl [211], Kmerator[212], Kounta[213], Krust[214], Meryl[46], MSPKmerCounter[215],…”

“Additionally, k-mers are utilized to identify antigenic regions and potential epitopes within protein sequences [155,156].”

“In contrast, many studies have suggested that the hypermutability of CpG dinucleotides is an insufficient explanation for nullomer origin [164,167].”

“The absence of specific five and six amino acid peptide combinations in publicly available proteome sequences has previously been identified [184,185], and there is potential enhancement of immunomodulatory effects and immunogenicity when incorporating these rare sequences into the development of…”

“However, Kmer-db is roughly 26 times faster than Mash and is subsequently better equipped to process larger datasets [121].”

“In light of the observed correlation between the strength of immune response and the prevalence of specific amino acid sequences in nature [179,180], it is hypothesized that nullomers and nullpeptides display heightened immunogenicity and therefore reinforce host defenses against pathogens (Fig.”

“COBS[49], DiscoverY[227], HowDeSBT[228], KmerGO [229], Kmerind[230], Mantis [231], MetaGraph[232], PAC [233], RecoverY[234], SBT [235], SeqOthello[236], SSHash[237], VarGeno[238] Genome Assembly In de novo genome assembly, sequencing reads undergo fragmentation into k-mers, and their overlaps are…”

“Quantifying shared and unique k-mers across meta-proteomic samples helps identify similarities and differences in protein expression profiles, enabling comparisons of microbial communities under different environmental conditions or between healthy and diseased states [151].”

“Recent clinical investigations highlight the potential of peptide-based drugs in cancer therapy, emphasizing advantages such as their small size, specificity, efficacy across a broad spectrum of cancers, potentially selective cytotoxicity, and cost-effectiveness [188,189].”

“Metaproteomic datasets contain a vast array of protein sequences from diverse and unlabeled organisms, posing significant challenges for accurate identification and functional interpretation [147,148].”

“By examining the empirical frequencies of k-mers, the GC-content, CpG suppression, repeat content, heterozygosity, and sequencing coverage of the sample can be inferred [51, 56, 57].”

“1C) [22, 28, 29], with certain nullpeptides even exhibiting cancer cell-killing properties [30,31].”

“Their absence has been attributed to detrimental effects on an organism, higher mutation rates, and stochastic effects [162 – 164].”

“COBS[49], DiscoverY[227], HowDeSBT[228], KmerGO [229], Kmerind[230], Mantis [231], MetaGraph[232], PAC [233], RecoverY[234], SBT [235], SeqOthello[236], SSHash[237], VarGeno[238] Genome Assembly In de novo genome assembly, sequencing reads undergo fragmentation into k-mers, and their overlaps are…”

“3E) [161].”

“1C) [22, 28, 29], with certain nullpeptides even exhibiting cancer cell-killing properties [30,31].”

“In light of the observed correlation between the strength of immune response and the prevalence of specific amino acid sequences in nature [179,180], it is hypothesized that nullomers and nullpeptides display heightened immunogenicity and therefore reinforce host defenses against pathogens (Fig.”

“…alignment algorithms have been utilized in detecting and filtering out contamination by comparing observed k-mers against a BFCounter[201], CHTKC [202], Discount[203], DSK2 [204], GECKO[205], Gerbil [206], Jellyfish2[8], KAnalyze [207], KCMBT[208], KCOSS [209], KHMer[210], KMC3 [45],…”

“COBS[49], DiscoverY[227], HowDeSBT[228], KmerGO [229], Kmerind[230], Mantis [231], MetaGraph[232], PAC [233], RecoverY[234], SBT [235], SeqOthello[236], SSHash[237], VarGeno[238] Genome Assembly In de novo genome assembly, sequencing reads undergo fragmentation into k-mers, and their overlaps are…”

“Repetitive elements are characterized by high k-mer counts [37,38].”

“K-mers can be utilized to label these individual sequences, facilitating meta-barcoding across various organisms or individual cells [133].”

“COBS[49], DiscoverY[227], HowDeSBT[228], KmerGO [229], Kmerind[230], Mantis [231], MetaGraph[232], PAC [233], RecoverY[234], SBT [235], SeqOthello[236], SSHash[237], VarGeno[238] Genome Assembly In de novo genome assembly, sequencing reads undergo fragmentation into k-mers, and their overlaps are…”

“k -mer encoding is a strategy in which contiguous sequences of k nucleotides are treated as single tokens [54].”

“A coverage distribution with a long tail of high coverage could indicate many loci of collapsed repeats in the assembly [187].”

“Several studies reveal the significant enhancements in prediction performance from data augmentation on genomic data that are small but high-dimensional in nature [145–148], which may have thousands of categories (e.g. k-mer analysis) [149, 150].”

“It has been observed that certain k-mer patterns or frequencies might be biologically meaningful, representing functional elements or genetic signatures associated with particular phenotypes or functions [19].”

“Minimizers are used in many bioinformatic applications, including sequence alignment, genome assembly, and data compression (Zheng et al. 2023, Moeckel et al. 2024, Ndiaye et al. 2024).”

“Computational-based methods, such as k-mer, PSSM, and structure-based methods like TS and SPSSC, excel in capturing local patterns and structural features, making them ideal for sequence analysis and structure prediction, though limited by high-dimensionality and local focus [28].”

“To simplify computation, we use K -mers [29] frequency vector as a representation of every sequence and compute pairwise distance based on these vectors.”

“Additionally, we incorporated advanced representations, including evolutionary scale modeling (ESM), sequence-based tokenization methods (Sequence tokens), and k -mers ( k = 3) feature extraction techniques [41], to comprehensively characterize the peptide sequences.”

“Bioinformatics is a field where data often naturally appears in bitstring format, for example to encode DNA, or study the effect of compounds on genes [44, 45].”

“Optimal k-mer Size and Computational Considerations Interestingly, the optimal k -mer window size for our gLMs differed from traditional k -mer analyses, where larger k values generally lead to improved accuracy (Moeckel et al 2024; Shaw and Yu 2022).”

“A number of initial methods have taken an ad-hoc approach to determine the values of “k” but lately more comprehensive computational approaches have been discussed to strike a tradeoff between computational complexity and biological signal [14].”

“Additionally, indexes like the r-index scale better with large datasets [40].”

“However, K-mer distribution patterns are also considered as the reflections of inherent genomic characteristics [20], and repetitive components may contribute to the polyploidy illusion observed in K-mer spectra.”

“In bioinformatics, k-mer was first widely used to process biological sequences such as DNA and RNA [43].”

“…the scale of these efforts and the development of diverse computational approaches, including homology-based annotation[5], k-mer–based taxonomic methods[6], and machine-learning frameworks[7], we remain limited in our ability to reliably predict the functional consequences of genomic variation.”

“Species ID was conducted using kmer analysis, a method which extracts and counts short DNA sequences from FASTQ files 70 .”

“Motifs refer to short patterns in DNA, RNA, or protein sequences that carry biological information (Moeckel et al. 2024).”

“Whilelarger k valuespreservedatagranularityand capture more information, they also increase input dimensionality and lead to sparser k -mer counts, potentially leading to over fi tting 26 .”

“Due to their high information content, k-mers have been used across many applications in computational biology, including tasks such as classification, motif discovery, or alignment-free sequence comparison [18].”

“Since k -mer frequencies are used in various bioinformatics domains [16], compressed k -mer images can be implemented in those analysis.”

“Despite their straightforward nature, k -mers are widely employed in various analytical and predictive tasks in computational biology and remain a popular feature engineering technique for machine learning models [42].”

“Similarly,k-mer-basedmethodsenablerapid,alignment-freecom-parison of sequences and have been widely used for taxonomic classification and similarity estimation [11, 12, 13].”

“In the field of bioinformatics, k-mer is a simple but powerful method for analyzing sequence, which is used to express the occurrence frequency of k neighbouring nucleic acids 41 .”

“4.1 T OKENIZERS K-mer tokenizer: A k-mer is a substring of length k from a DNA or RNA sequence (Moeckel et al., 2024).”

“The k-mer-based analysis provides a powerful, efficient, and versatile approach as it allows for sequence analysis without the need for alignment, enabling rapid comparisons and assessments of metagenomic data with less computational resources and more accuracy (Moeckel et al. 2024).”

“K-mer-based methods convert sequences into numerical representations, capturing key microbial genomic features while significantly enhancing processing efficiency and information extraction, advancing genomic data analysis [24].”

“In particular, sequence features are extracted from each k-mer (a subsequence with length k ) using the Word2Vec approach [31].”

“Methods for efficient and sensitive taxonomic classification of metagenomic sequences have addressed similar challenges in computational efficiency of taxonomic assignment by using k -mer based approaches, which are faster than alignments [20].”

“In the k-mer--based approach, sequences are parsed into overlapping fragments of length k , and the frequency of each unique k-mer is calculated to generate a feature vector that captures short-range dependencies be-tween residues [40].”

“K-mer [36] slicing is utilized to process lncRNA and miRNA sequences, applying 3-mers for longer lncRNAs and 2-mers for shorter miRNAs.”

“Although the model with k = 4 exhibits superior performance compared to that with k = 3, the sparse 4-mer count may result in severe overfitting [15].”

“Other frequently used techniques, such as qPCR [8, 9], k-mer-based approaches [10] and genome assembly, also present drawbacks, such the need for species-specific optimization for qPCR, lack of precision of k-mer based approaches, and assembler-specific variations in behavior when dealing with…”

“This encoding effectively preserves genomic patterns that are essential for distinguishing genotypic variations 28 .”

“To identify short sequence patterns associated with specific AMP functions, we performed one-versus-rest k-mer enrichment analysis on the benchmark dataset [ 82, 83].”

“In addition, Colbran and colleagues constructed a k -mer-support vector machine (SVM) machine learning framework and found that the occurrence patterns of short sequence motifs can correctly predict widely active human enhancers 18,21 .”

“However, the search for protein coding regions at the heart of Codetta is replaced by lookup of short peptides (amino acid k-mers; other k-mer approaches in bioinformatics have been recently reviewed (11)) in a reference table representing conserved sequences in protein families.”

“…fundamental approaches: (i) determining Single-Nucleotide Variants (SNVs) relative to a reference genome, (ii) measuring sequence similarity based on short subsequences of length k , known as k -mers [10], and (iii) comparing the strains’ gene content, referred to as gene-by-gene methods (GbG) [9].”

“While the concept has precedent in biology (e.g. k-mers [49]) and linguistics [50], n-gram analysis gained global prominence with Michel et al.'s study [51], which examined the frequency of n-grams in about 4% of all books ever published using the Google Books corpus and assumed that n-grams can be…”

“This approach is particularly useful for species where high-quality reference genomes are either unavailable or dif fi cult to obtain (Moeckel et al., 2024).”

“Most of these methods are based on DNA, RNA or protein k-mers exact matching or statistics [9,12–14 , To this goal, we explored the feasibility of utilizing an integral parameter that characterizes the proteome or its subsets (protein groups), specifically the occurrence of short fragments of…”

“Sequence k-mers are short substrings of equal length that allow for exact matching between read and reference (10).”

“K-mers are short, contiguous nucleotide sequences of length k, and have a number of biological applications [3,4].”

“Previous studies experimenting with different k -mer values have shown that GC-rich genomes generally benefit from smaller k -values, whereas larger k-values are more suitable for AT-rich genomes to potentially resolve the repeat regions effectively [39–41].”

“Genomes and proteomes are composed of nucleotide or peptide sequences, respectively, which can be divided into fixed-length substrings called k-mers, where k represents the specified length [5].”

“Although a large body of literature has explored the applications of k-mers in various bioinformatics tasks [13] , there is still a lack of systematic research on how to choose an appropriate k value in practical scenarios.”

“K-mer K-mer [ 113] is a typical method employed in this context, where a long sequence of nucleotides is analyzed as contiguous subsequences of length K. K-mers facilitate faster sequence comparisons by breaking down sequences into smaller, more manageable pieces, which is particularly useful in…”

“This approach enabled the identification of the k nearest neighbors for each sequence, capturing patterns in DNA sequences based on k-mer distributions, thereby aiding in classification or clustering tasks [12].”

“The k -mer frequency, calculated from the occurrence of k - mer terms in sequences of an organism, does not depend on the total length of the sequences and therefore enables comparison between different organisms in a variety of applications [16].”

“This study employs a alignment-free k-mer sequence representation method [36], converting nucleotide sequences into k-mer features.”

“GCG For example, a sequence 𝑆𝑆 𝑆 “ATGCGT” with 𝑘𝑘 𝑘 𝑘 generates the K-mers ATG, TGC, , CGT . genomic for This representation captures features crucial identifying genotypic variations 35 .”

“Initial steps of k-mer analysis, such as counting and frequency estimation, have been well-established through efficient tools (Moeckel et al., 2024) that can process large genomic datasets using optimized memory structures including Bloom filters and minimizers.”

“57 Notably,theseapplicationsofk-mersaredif-ferent than the approach we implemented; in most of these settings, k-mersareuseddirectlyfromrawsequencereads(priortovariantcall-ing).”

“…with tools such as BLAST [1], motif discovery with methods such as MEME [2], probabilistic sequence models such as hidden Markov models [3], explicit sequence representations based on k-mer composition [4], and supervised predictive methods built on related representations, such as gkm-SVM [5].”

“…the formation of repeats and secondary structures, while ensuring uniform melting temperatures and adhering to GC content constraints (Johnson et al. 2023). k -mers are short sequences of length k , and are fundamental units in various biological analyses and applications (Moeckel et al. 2024).”

“…this k-mer transition, we focus on the analysis of codon usage amelioration since it greatly impacts the success of HGTs in bacteria [77,78], and there is a relationship between k-mer profiles and compositional biases in nucleotide sequences linked directly or indirectly to codon usage [79–82].”

“IRESFinder [21] employs k-mer features [22–24] to differentiate IRES using logistic regression models; however, it is limited to predicting human IRES.”

“In de Bruijn graph approaches, reads are split into 𝑘 -mers, and edges represent observed adjacencies between 𝑘 -mers [9].”

“Conversely, higher k-values reduce repetitive sequence interference and improve mapping speci fi city but are more susceptible to base-calling errors or insuf fi cient coverage, leading to k-mer misrepresentation and compromised analytical accuracy (Moeckel et al., 2024; Roberts et al., 2025).”

“Mapping-free algorithms are computationally inexpensive and can run substantially faster than mapping-based methods [ 20 ].”

“This topic is extensively described in (Moeckel et al. 2024).”

“This representation is widely adopted in bioinformatics because it captures local sequence patterns without requiring alignment and scales naturally to varying-length sequences [18].”

“Such local nucleotide dependencies also underlie many classical sequence representations, including k -mer-based approaches [ 17 ].”

“Although k-mer based analyses have helped alleviate some assembly challenges (reviewed in (Moeckel et al., 2024)) and have proven useful for characterizing satDNA arrays (Wei et al., 2014) and assessing polymorphism among individuals in human populaJons (Altemose et al., 2014), accurately mapping…”