Coding for Multiple Reverse-Complement and Palindromic Duplications
Abstract
Reverse-complement (RC) and palindromic (PAL) duplications copy a length-k block, reverse the copy, and insert it immediately after the original block; an RC duplication also complements the copied symbols. We study q-ary codes correcting t such operations performed sequentially, so a later operation may copy symbols created by an earlier one. For fixed q≥2 and k,t≥1, every length-n code C for either channel satisfies n−logq|C|≥ tlogq n−Oq,k,t(1); for fixed q,k and 1≤ t=t(n)=o(n) the lower bound is tlogq(n/t)−Oq,k(t). For a single RC error over an even alphabet with a fixed-point-free complement, the previously known RC-specific construction applies at odd k and does not cover even k. For every even k and any involutive complement, we give a coordinate-wise bijection that turns each RC duplication into a PAL duplication. Applying this bijection to every codeword therefore converts any t-error-correcting RC code into a PAL code of the same size, and conversely; encoders and decoders transfer by adding linear-time coordinate passes. For every even k, we also determine the maximum number of distinct descendants produced by exactly two errors from one source word. Words alternating between any two distinct alphabet symbols attain this maximum for PAL, and the bijection gives the RC maximizers. For both PAL and RC at fixed even k, we prove the existence of two-error-correcting codes with redundancy 4logq n+Oq,k(1). In the binary two-error problem, the converse gives 2log2 n−Ok(1), leaving a factor-two gap in the best existence bounds.
Related
BibTeX
@misc{zabokritskiy2026coding,
title = {{Coding for Multiple Reverse-Complement and Palindromic Duplications}},
author = {Aryeh Lev Zabokritskiy},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00779},
eprint = {2609.00779},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00779},
}
RIS
TY - UNPB
TI - Coding for Multiple Reverse-Complement and Palindromic Duplications
AU - Aryeh Lev Zabokritskiy
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.00779
UR - https://arxiv.org/abs/2609.00779
AB - Reverse-complement (RC) and palindromic (PAL) duplications copy a length-k block, reverse the copy, and insert it immediately after the original block; an RC duplication also complements the copied symbols. We study q-ary codes correcting t such operations performed sequentially, so a later operation may copy symbols created by an earlier one. For fixed q≥2 and k,t≥1, every length-n code C for either channel satisfies n−log_q|C|≥ tlog_q n−O_q,k,t(1); for fixed q,k and 1≤ t=t(n)=o(n) the lower bound is tlog_q(n/t)−O_q,k(t). For a single RC error over an even alphabet with a fixed-point-free complement, the previously known RC-specific construction applies at odd k and does not cover even k. For every even k and any involutive complement, we give a coordinate-wise bijection that turns each RC duplication into a PAL duplication. Applying this bijection to every codeword therefore converts any t-error-correcting RC code into a PAL code of the same size, and conversely; encoders and decoders transfer by adding linear-time coordinate passes. For every even k, we also determine the maximum number of distinct descendants produced by exactly two errors from one source word. Words alternating between any two distinct alphabet symbols attain this maximum for PAL, and the bijection gives the RC maximizers. For both PAL and RC at fixed even k, we prove the existence of two-error-correcting codes with redundancy 4log_q n+O_q,k(1). In the binary two-error problem, the converse gives 2log_2 n−O_k(1), leaving a factor-two gap in the best existence bounds.
ER -