Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2410.16968 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909405237215232 |
|---|---|
| author | Golan, Shay Shur, Arseny M. |
| author_facet | Golan, Shay Shur, Arseny M. |
| contents | 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\ge2$ 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 $\mathcal{DR}_σ(k,w)$ besides the fact that it is close to $\frac{2}{w+1}$ unless $w\gg k$.
We first show that $\mathcal{DR}_σ(k,w)$ can be computed in $O(kσ^{k+w})$ time. Then we attend to the case $w\le k$ and present a formula that allows one to compute $\mathcal{DR}_σ(k,w)$ in just $O(w \log w)$ time. Further, we describe the behaviour of $\mathcal{DR}_σ(k,w)$ in this case, establishing the connection between $\mathcal{DR}_σ(k,w)$, $\mathcal{DR}_σ(k+1,w)$, and $\mathcal{DR}_σ(k,w+1)$. In particular, we show that $\mathcal{DR}_σ(k,w)<\frac{2}{w+1}$ (by a tiny margin) unless $w$ is small. We conclude with some partial results and conjectures for the case $w>k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_16968 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Expected Density of Random Minimizers Golan, Shay Shur, Arseny M. Combinatorics Genomics 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\ge2$ 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 $\mathcal{DR}_σ(k,w)$ besides the fact that it is close to $\frac{2}{w+1}$ unless $w\gg k$. We first show that $\mathcal{DR}_σ(k,w)$ can be computed in $O(kσ^{k+w})$ time. Then we attend to the case $w\le k$ and present a formula that allows one to compute $\mathcal{DR}_σ(k,w)$ in just $O(w \log w)$ time. Further, we describe the behaviour of $\mathcal{DR}_σ(k,w)$ in this case, establishing the connection between $\mathcal{DR}_σ(k,w)$, $\mathcal{DR}_σ(k+1,w)$, and $\mathcal{DR}_σ(k,w+1)$. In particular, we show that $\mathcal{DR}_σ(k,w)<\frac{2}{w+1}$ (by a tiny margin) unless $w$ is small. We conclude with some partial results and conjectures for the case $w>k$. |
| title | Expected Density of Random Minimizers |
| topic | Combinatorics Genomics |
| url | https://arxiv.org/abs/2410.16968 |