MacKay-Neal codes improve accuracy of DNA data decoding
MacKay-Neal Codes for DNA Channels under Block-MAP Decoding
Information Theory
Summary
Reading data stored in DNA is tricky because the sequences can have errors like extra, missing, or changed pieces. The authors found a way to use special error-correcting codes called MacKay-Neal codes to fix these errors more reliably, even when the mistakes can be quite complicated. They proved mathematically that their method can recover the original data almost perfectly as DNA sequences get longer, without needing to know exactly where errors happen. This helps to store and read information from DNA more accurately.
What this means in practice
- •For bioinformatics engineers: Improve DNA data storage reliability by applying MacKay-Neal codes for error correction in noisy DNA reads without explicit sequence alignment.
- •For communications system designers: Design error-correcting codes for channels with insertion, deletion, and substitution errors based on proven theoretical performance guarantees.
A theory result. No direct application yet.
Authors
Kenta Kasai
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.