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 + \Omega(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 \leq \min\{(\ell-1)/2,(\ell+2)/3\}$. The first construction relies on generalized Reed-Solomon codes and has redundancy $2t\log_q n + \Theta(\log\log n)$. The second is based on Sidon sets (or rather $B_t$ sequences) and has redundancy $t\log_q n + \Theta(\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 \leq \min\{(\ell-1)/4,(\ell+2)/6\}$, this gives explicit $t$-edit-correcting codes with redundancy $t\log_q n + \Theta(\log\log n)$, which is first-order optimal.
Blogger's Review: The proposed error-correcting code constructions for adversarial nanopore channels exhibit a strong interplay between theory and practice, particularly in their flexibility and efficiency in handling edits. The detailed analysis of redundancy provides a solid foundation for further research, making it a noteworthy contribution.