On the Asymptotic Rate of Optimal Codes that Correct Tandem Duplications for Nanopore Sequencing
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910566787842048 |
|---|---|
| author | Yu, Wenjun Ye, Zuo Schwartz, Moshe |
| author_facet | Yu, Wenjun Ye, Zuo Schwartz, Moshe |
| contents | We study codes that can correct backtracking errors during nanopore sequencing. In this channel, a sequence of length $n$ over an alphabet of size $q$ is being read by a sliding window of length $\ell$, where from each window we obtain only its composition. Backtracking errors cause some windows to repeat, hence manifesting as tandem-duplication errors of length $k$ in the $\ell$-read vector of window compositions. While existing constructions for duplication-correcting codes can be straightforwardly adapted to this model, even resulting in optimal codes, their asymptotic rate is hard to find. In the regime of unbounded number of duplication errors, we either give the exact asymptotic rate of optimal codes, or bounds on it, depending on the values of $k$, $\ell$ and $q$. In the regime of a constant number of duplication errors, $t$, we find the redundancy of optimal codes to be $t\log_q n+O(1)$ when $\ell|k$, and only upper bounded by this quantity otherwise. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_08223 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Asymptotic Rate of Optimal Codes that Correct Tandem Duplications for Nanopore Sequencing Yu, Wenjun Ye, Zuo Schwartz, Moshe Information Theory We study codes that can correct backtracking errors during nanopore sequencing. In this channel, a sequence of length $n$ over an alphabet of size $q$ is being read by a sliding window of length $\ell$, where from each window we obtain only its composition. Backtracking errors cause some windows to repeat, hence manifesting as tandem-duplication errors of length $k$ in the $\ell$-read vector of window compositions. While existing constructions for duplication-correcting codes can be straightforwardly adapted to this model, even resulting in optimal codes, their asymptotic rate is hard to find. In the regime of unbounded number of duplication errors, we either give the exact asymptotic rate of optimal codes, or bounds on it, depending on the values of $k$, $\ell$ and $q$. In the regime of a constant number of duplication errors, $t$, we find the redundancy of optimal codes to be $t\log_q n+O(1)$ when $\ell|k$, and only upper bounded by this quantity otherwise. |
| title | On the Asymptotic Rate of Optimal Codes that Correct Tandem Duplications for Nanopore Sequencing |
| topic | Information Theory |
| url | https://arxiv.org/abs/2408.08223 |