pipette
ESEspañol

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

Kenta Kasai

Preprint

In the authors' words

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 , the socket ensemble, with one transmitted bit fixed and an independent uniform known offset, has limiting rate bits per stored nucleotide. If the joint SIR of a fixed number of reads under independent, uniformly distributed input nucleotides exceeds , the ensemble-average full extended-word block error is , and deterministic graph-offset sequences attain the same limiting rate and message-average error bound. This result concerns the discrete rate family , 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.

Main resultLimitation the authors admit

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 14 pages