Swiftly identifying strongly unique k-mers

Zentgraf, Jens, Rahmann, Sven
Algorithms for Molecular Biology · Springer Nature · 2025-07-13 · DOI: 10.1186/s13015-025-00286-6

Abstract

Motivation Short DNA sequences of length k that appear in a single location (e.g., at a single genomic position, in a single species from a larger set of species, etc.) are called unique k-mers . They are useful for placing sequenced DNA fragments at the correct location without computing alignments and without ambiguity. However, they are not necessarily robust: A single basepair change may turn a unique k -mer into a different one that may in fact be present at one or more different locations, which may give confusing or contradictory information when attempting to place a read by its k -mer content. A more robust concept are strongly unique k -mers, i.e., unique k -mers for which no Hamming-distance-1 neighbor with conflicting information exists in all of the considered sequences. Given a set of k -mers, it is therefore of interest to have an efficient method that can distinguish k -mers with a Hamming-distance-1 neighbor in the collection from those that do not. Results We present engineered algorithms to identify and mark within a set K of (canonical) k -mers all elements that have a Hamming-distance-1 neighbor in the same set. One algorithm is based on recursively running a 4-way comparison on sub-intervals of the sorted set. The other algorithm is based on bucketing and running a pairwise bit-parallel Hamming distance test on small buckets of the sorted set. Both methods consider canonical k -mers (i.e., taking reverse complements into account) and allow for efficient parallelization. The methods have been implemented and applied in practice to sets consisting of several billions of k -mers. An optimized combined approach running with 16 threads on a 16-core workstation yields wall times below 20 seconds on the 2.5 billion distinct 31-mers of the human telomere-to-telomere reference genome. Availability An implementation can be found at https://gitlab.com/rahmannlab/strong-k-mers .

Read at publisher →

Similar articles