Ok-k-mer: Selecting k-mer length ensembles for calculating genomic distance
- 1Johns Hopkins University
Abstract
Current methods for computing sequence similarity across large groups of genome sequences tend to do so at the level of k-mers since this is far more efficient than base-by-base alignment. While these methods use default k-mer lengths, recent work shows that the particular choice of k-mer length greatly affects accuracy, and that using multiple values of k can boost accuracy relative to the best single choice of k, particularly when the goal is to estimate genomic distances that reflect true phylogenetic relationships. Here, we introduce Ok-k-mer, a tool to systematically select weighted k-mer length ensembles for pairwise genomic distance estimation, thereby increasing the accuracy of those estimates. Given a phylogenetic tree, Ok-k-mer ranks genome pairs by Jaccard distance across a range of k and uses a progressive search to maximize the Spearman correlation, {rho}, between weighted-average k-mer ranks and branch distances. Across eight Genome Taxonomy Database datasets, Ok-k-mer ensembles improved correlation over standard default k-mer lengths. In the Chlamydiales taxonomy, a three-length ensemble k=(9,17,22) achieved a 23.9% relative improvement over the best single length (k=20) and a 36.7% improvement over a commonly used default of 31-mers. We demonstrate that Ok-k-mer k-mer length ensembles remain stable (i.e. lengths and weights change only moderately) under genome subsampling within a taxonomy but vary across datasets. Ok-k-mer can annotate all subtrees of a phylogeny, which reveals distinct patterns of ensembles reflecting potential differences in genome evolution. Ok-k-mer provides a framework for moving beyond a "one-k-fits-all" k-mer analysis, improving genomic distance estimation in the era of massive-scale genomics.
Related
- Integrative Genomic Analyses Identify and Prioritize Candidate Loci for Metatarsal Length and Circumference in Broilers.
- Persistence of viral full-length genomic RNA and replication-associated RNA transcripts and proteins in sheep tissues following acute Crimean-Congo hemorrhagic fever virus infection
- Atlas of Proteomic Technologies: an evidence-based framework for selecting and combining commercial proteomics platforms
- Selecting for lysis in a temperate phage population
- Comparative assessment of two participatory approach methods for selecting pig health indicators: A proof-of-concept on respiratory health
BibTeX
@misc{hwang2026okkmer,
title = {{Ok-k-mer: Selecting k-mer length ensembles for calculating genomic distance}},
author = {S. Hwang and B. Langmead},
howpublished = {bioRxiv},
year = {2026},
month = nov,
doi = {10.64898/2026.11.06.764926},
url = {https://www.biorxiv.org/content/10.64898/2026.11.06.764926v1},
note = {CC BY-NC},
}
RIS
TY - UNPB
TI - Ok-k-mer: Selecting k-mer length ensembles for calculating genomic distance
AU - S. Hwang
AU - B. Langmead
PY - 2026
DA - 2026/11/06
PB - bioRxiv
DO - 10.64898/2026.11.06.764926
UR - https://www.biorxiv.org/content/10.64898/2026.11.06.764926v1
AB - Current methods for computing sequence similarity across large groups of genome sequences tend to do so at the level of k-mers since this is far more efficient than base-by-base alignment. While these methods use default k-mer lengths, recent work shows that the particular choice of k-mer length greatly affects accuracy, and that using multiple values of k can boost accuracy relative to the best single choice of k, particularly when the goal is to estimate genomic distances that reflect true phylogenetic relationships. Here, we introduce Ok-k-mer, a tool to systematically select weighted k-mer length ensembles for pairwise genomic distance estimation, thereby increasing the accuracy of those estimates. Given a phylogenetic tree, Ok-k-mer ranks genome pairs by Jaccard distance across a range of k and uses a progressive search to maximize the Spearman correlation, {rho}, between weighted-average k-mer ranks and branch distances. Across eight Genome Taxonomy Database datasets, Ok-k-mer ensembles improved correlation over standard default k-mer lengths. In the Chlamydiales taxonomy, a three-length ensemble k=(9,17,22) achieved a 23.9% relative improvement over the best single length (k=20) and a 36.7% improvement over a commonly used default of 31-mers. We demonstrate that Ok-k-mer k-mer length ensembles remain stable (i.e. lengths and weights change only moderately) under genome subsampling within a taxonomy but vary across datasets. Ok-k-mer can annotate all subtrees of a phylogeny, which reveals distinct patterns of ensembles reflecting potential differences in genome evolution. Ok-k-mer provides a framework for moving beyond a "one-k-fits-all" k-mer analysis, improving genomic distance estimation in the era of massive-scale genomics.
ER -