On the Palindromic/Reverse-Complement Duplication Correcting Codes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917239506075648 |
|---|---|
| author | Sun, Yubo Ge, Gennian |
| author_facet | Sun, Yubo Ge, Gennian |
| contents | Motivated by applications in in-vivo DNA storage, we study codes for correcting duplications. A reverse-complement duplication of length $k$ is the insertion of the reversed and complemented copy of a substring of length $k$ adjacent to its original position, while a palindromic duplication only inserts the reversed copy without complementation. We first construct an explicit code with a single redundant symbol capable of correcting an arbitrary number of reverse-complement duplications (respectively, palindromic duplications), provided that all duplications have length $k \ge 3\lceil \log_q n \rceil$ and are disjoint. Next, we derive a Gilbert-Varshamov bound for codes that can correct a reverse-complement duplication (respectively, palindromic duplication) of arbitrary length, showing that the optimal redundancy is upper bounded by $2\log_q n + \log_q\log_q n + O(1)$. Finally, for $q \ge 4$, we present two explicit constructions of codes that can correct $t$ length-one reverse-complement duplications. The first construction achieves a redundancy of $2t\log_q n + O(\log_q\log_q n)$ with encoding complexity $O(n)$ and decoding complexity $O\big(n(\log_2 n)^4\big)$. The second construction achieves an improved redundancy of $(2t-1)\log_q n + O(\log_q\log_q n)$, but with encoding and decoding complexities of $O\big(n \cdot \mathrm{poly}(\log_2 n)\big)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_01151 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Palindromic/Reverse-Complement Duplication Correcting Codes Sun, Yubo Ge, Gennian Information Theory Motivated by applications in in-vivo DNA storage, we study codes for correcting duplications. A reverse-complement duplication of length $k$ is the insertion of the reversed and complemented copy of a substring of length $k$ adjacent to its original position, while a palindromic duplication only inserts the reversed copy without complementation. We first construct an explicit code with a single redundant symbol capable of correcting an arbitrary number of reverse-complement duplications (respectively, palindromic duplications), provided that all duplications have length $k \ge 3\lceil \log_q n \rceil$ and are disjoint. Next, we derive a Gilbert-Varshamov bound for codes that can correct a reverse-complement duplication (respectively, palindromic duplication) of arbitrary length, showing that the optimal redundancy is upper bounded by $2\log_q n + \log_q\log_q n + O(1)$. Finally, for $q \ge 4$, we present two explicit constructions of codes that can correct $t$ length-one reverse-complement duplications. The first construction achieves a redundancy of $2t\log_q n + O(\log_q\log_q n)$ with encoding complexity $O(n)$ and decoding complexity $O\big(n(\log_2 n)^4\big)$. The second construction achieves an improved redundancy of $(2t-1)\log_q n + O(\log_q\log_q n)$, but with encoding and decoding complexities of $O\big(n \cdot \mathrm{poly}(\log_2 n)\big)$. |
| title | On the Palindromic/Reverse-Complement Duplication Correcting Codes |
| topic | Information Theory |
| url | https://arxiv.org/abs/2602.01151 |