MacKay-Neal Codes for DNA Channels under Block-MAP Decoding

Abstract

We prove achievability below the symmetric information rate (SIR) under block maximum a posteriori (MAP) decoding for a fixed-degree MacKay-Neal (MN) socket ensemble on the quaternary insertion-deletion-substitution channel used to model DNA reads. For every integer $\ell\ge4$, the $(\ell,3,3)$ socket ensemble, with one transmitted bit fixed and an independent uniform known offset, has limiting rate $r_\star=6/\ell$ bits per stored nucleotide. If the joint SIR $J_t$ of a fixed number $t$ of reads under independent, uniformly distributed input nucleotides exceeds $r_\star$, the ensemble-average full extended-word block error is $O(1/n)$, and deterministic graph-offset sequences attain the same limiting rate and message-average error bound. This result concerns the discrete rate family $6/\ell$, not arbitrary rates approaching a given SIR. The channel permits arbitrarily many insertions and unbounded drift, with no alignment supplied to the receiver. The proof combines established MN parity and distance estimates with a strict arbitrary-candidate-list bound and a list construction that accounts for hidden output boundaries.