First-order optimal codes for an adversarial nanopore channel

Abstract

We study error-correcting codes for an adversarial nanopore channel, where a $q$-ary string is first transformed by an inter-symbol interference channel with window size $\ell$ into a sequence of overlapping $\ell$-mers, and an adversary then corrupts this $\ell$-mer sequence by introducing at most $t$ edits. For the deletion-only nanopore channel, we show that the optimal redundancy of $t$-deletion-correcting codes of length $n$ lies between $t{\log }_{q}n+\hat{I}\text{c◯}(1)$ and $2t{\log }_{q}n-{\log }_q{\log }_{2}n+O(1)$. We then give two explicit deletion-correcting constructions in the regime $t\le \min \{(\ell -1)/2,(\ell +2)/3\}$. The first construction relies on generalized Reed-Solomon codes and has redundancy $2t{\log }_{q}n+\hat{I}˜(\log \log n)$. The second is based on Sidon sets (or rather $B_t$ sequences) and has redundancy $t{\log }_{q}n+\hat{I}˜(\log \log n)$, matching the lower bound to first order. We further extend the $B_t$-based approach to the edit channel, allowing insertions, deletions, and substitutions of $\ell$-mers. In the regime $t\le \min \{(\ell -1)/4,(\ell +2)/6\}$, this gives explicit $t$-edit-correcting codes with redundancy $t{\log }_{q}n+\hat{I}˜(\log \log n)$, which is first-order optimal.

Updated title and abstract. Added order-optimal constructions. Corrected the constraint on $t$