2024/10/22 by Shay Golan, Golan, Shay, Arseny M. Shur +1 · 1 citation
Computer Science · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Biological sciences #FOS: Mathematics #Genomics (q-bio.GN)
paper · pdf · doi:10.48550/arxiv.2410.16968
openalex publication_date 2024/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Minimizer schemes, or just minimizers, are a very important computational primitive in sampling and sketching biological strings. Assuming a fixed alphabet of size σ, a minimizer is defined by two integers k,w≥2 and a total order ρ on strings of length k (also called k-mers). A string is processed by a sliding window algorithm that chooses, in each window of length w+k-1, its minimal k-mer with respect to ρ. A key characteristic of the minimizer is the expected density of chosen k-mers among all k-mers in a random infinite σ-ary string. Random minimizers, in which the order ρ is chosen uniformly at random, are often used in applications. However, little is known about their expected density DRσ(k,w) besides the fact that it is close to (2)/(w+1) unless w≫ k. We first show that DRσ(k,w) can be computed in O(kσk+w) time. Then we attend to the case w≤ k and present a formula that allows one to compute DRσ(k,w) in just O(w log w) time. Further, we describe the behaviour of DRσ(k,w) in this case, establishing the connection between DRσ(k,w), DRσ(k+1,w), and DRσ(k,w+1). In particular, we show that DRσ(k,w)<(2)/(w+1) (by a tiny margin) unless w is small. We conclude with some partial results and conjectures for the case w>k.