Source-linked AI summary
Marker-Delimited Codes for Short-Blocklength, High-Rate Coding over Multi-Read Edit Channels
Sinan Ates Yercan, Marc Antonini, Serge Kas Hanna
TL;DR
DNA storage retrieval must handle multiple noisy reads containing substitution, insertion, and deletion errors while using short, costly oligos with low redundancy. The paper combines marker-delimited inner coding with outer LDPC belief-propagation decoding, reporting faster and more reliable decoding in the short-blocklength, high-rate regime.
Problem
Short, costly DNA oligos and combined insertion, deletion, and substitution errors create a need for low-overhead error correction for reliable storage retrieval.
Method
The scheme uses MDC to segment reads and generate symbolwise APPs, then supplies them as soft information to an outer LDPC decoder.
Results
The proposed construction achieves faster and more reliable decoding than existing approaches in the short-blocklength, high-rate regime.
Takeaways & Limitations
MDC-based constructions are reported as well suited to multi-read edit channels while maintaining practical decoding complexity.
Abstract
from arXiv · showhide
The read process of DNA-based data storage systems generates multiple noisy copies of the stored DNA sequences, affected by edit errors consisting of substitutions, deletions, and insertions. Motivated by the challenge of ensuring reliable data retrieval in the presence of edit errors, we present a concatenated coding scheme that accounts for practical design constraints in DNA storage. We introduce and apply the marker-delimited code (MDC) as the inner code, which enables fast and reliable computation of symbolwise a posteriori probabilities (APPs). We combine MDC with an outer LDPC code. The LDPC is decoded via belief propagation using the soft information generated by MDC. Our results show that, in comparison with prior work, this construction provides more efficient error correction over multi-read edit channels in the short-blocklength and high-rate regime.
I. INTRODUCTION
DNA storage faces substitution, insertion, and deletion errors, while short, costly oligos make low-overhead error correction important. The paper proposes an MDC–LDPC concatenated scheme for reliable, efficient decoding in the short-blocklength, high-rate regime.
- DNA synthesis and sequencing introduce insertion and deletion errors in addition to substitutions, collectively creating edit errors.
- Short DNA oligos, typically a few hundred nucleotides long, constrain code design and remain costly to synthesize.
- Low storage overhead is important because writing data into DNA dominates overall cost.
- The proposed scheme introduces the marker-delimited code as an inner code and combines it with an outer LDPC code.
- MDC decoding segments full reads into shorter independent subproblems, enabling parallel likelihood-based APP computation and soft information for LDPC belief propagation.
- The authors report faster and more reliable decoding than existing approaches in the short-blocklength, high-rate regime.
B. Multi-Read Edit Channel
The multi-read edit channel independently transforms a codeword into several noisy reads through insertion, deletion, substitution, or retention events. Drift tracks synchronization loss caused by insertions and deletions.
- The channel outputs t noisy reads independently by passing a codeword through random edit channels.
- Each input symbol undergoes insertion, deletion, substitution, or retention with probabilities p_i, p_d, p_s, and p_r.
- An insertion prepends a uniformly chosen quaternary symbol, substitution replaces the input with another quaternary symbol, retention preserves it, and deletion removes it.
- The drift vector measures synchronization loss as the cumulative difference between insertion and deletion events after each input symbol.
- The drift vector forms a Markov chain whose transitions increment, preserve, or decrement drift according to insertion, retention-or-substitution, and deletion.
III. CODING SCHEME
The proposed concatenated scheme uses MDC to generate symbolwise APPs over the multi-read edit channel and an outer quaternary LDPC code to decode using that soft information. At high rates, the construction is reported to be faster and more reliable than convolutional and marker-repeat inner codes.
- MDC generates symbolwise APPs over the multi-read edit channel, while the outer LDPC code uses those APPs for soft decoding.
- The LDPC soft-decoding procedures are adapted to the quaternary setting of the APPs produced by MDC.
- At high rates, MDC is reported to provide faster decoding and improved reliability than convolutional and marker-repeat inner codes.
A. Marker-Delimited Codes (MDC)
MDC partitions a message into independently encoded blocks and appends fixed markers that delimit segments. This structure enables parallel, tractable likelihood-based APP computation over short read fragments.
- An MDC partitions the information message into ν blocks, encodes each independently with a short code, and appends a fixed marker sequence to each block.
- Markers delimit the codeword into non-overlapping segments that the decoder can identify and isolate.
- Segmentation divides full-length multi-read APP computation into ν smaller subproblems over shorter segments.
- The segment subproblems can be processed independently and in parallel, reducing decoding time.
- Choosing a sufficiently small segment length B makes likelihood-based APP computation tractable.
B. Concatenated Architecture
The concatenated architecture uses MDC as an inner code to generate symbolwise APPs from multi-read edit-channel outputs, then supplies these soft values to an LDPC belief-propagation decoder.
- The LDPC parity-check matrix is constructed with the PEG method for regular LDPC codes.
- Random nonzero elements from F2^2 are assigned to nonzero parity-check entries, producing a nonbinary LDPC code.
- MDC generates symbolwise APPs over quaternary symbols from multiple channel reads.
- The outer LDPC code is decoded by belief propagation using the APPs produced by MDC.
IV. MDC SOFT-OUTPUT DECODING
MDC decoding follows a divide-and-conquer process that segments each read, computes likelihood-based APPs on short fragments, and refines boundaries using confidence values.
- The decoder sequentially performs segmentation, likelihood-based APP computation, and confidence-based boundary refinement.
- Static markers split each of the t reads into individual segments before fragment-level APP computation.
- Segmentation converts full multi-read decoding into smaller subproblems over short fragments that can be processed independently and in parallel.
- The approach avoids BCJR’s exponential complexity in the number of reads t for exact joint multi-read inference.
- Separating BCJR across reads or using Trellis BMA avoids exact joint inference but produces degraded APPs.
A. Segmentation
MDC segmentation estimates cumulative segment offsets caused by edit-induced drift, using a trellis and marker-dependent offset probabilities to locate segment boundaries.
- The received sequence y ∈Σ4^n′ is represented by an offset vector Z whose entries give net drift at MDC segment ends.
- Estimating Z is equivalent to segmentation because each difference Zj − Zj−1 equals the net offset introduced within segment j.
- The segment-offset probability conditions on the previous offset and combines codeword and marker offset contributions.
- Marker-offset probabilities are obtained analytically, or by enumerating error patterns when the marker length satisfies µ ≤ 4.
- A Viterbi-like trellis recursively computes allowable offsets, path metrics, predecessors, and final offset estimates.
B. Shortlisted Likelihood-Based APP Computation
MDC computes symbolwise APPs for short segments and reduces their cost by restricting likelihood calculations to candidates selected through κ-mer Jaccard similarity.
- For a segment, the decoder computes posterior probabilities over extended codewords and marginalizes them to obtain symbolwise APPs.
- Independent reads allow per-read likelihoods to be combined, with each likelihood computed by dynamic programming in O(B^2) time.
- Exact APP evaluation requires posterior computation for all |C′| = 4^k̃ codewords, each involving quadratic-time dynamic programming in segment length B.
- A linear-time κ-mer Jaccard similarity metric selects per-read shortlists, whose union forms the candidate set L.
- The decoder applies quadratic-time posterior calculations only to the |L| shortlisted candidates instead of all codewords.
- APP accuracy is retained when the shortlist captures most posterior mass, meaning Σx̃∈L Pr(x̃|ỹ[t]) is close to 1.
C. Confidence-Based Boundary Refinement
The decoder refines segmentation boundaries after initial APP computation because APP accuracy depends strongly on segmentation accuracy. It updates probabilities selectively using a confidence threshold and retains initial APPs when refinement does not improve confidence.
- C. Confidence-Based Boundary Refinement: After initial APP computation, the decoder evaluates a confidence score Fj for each segment j.The score is used to identify segments whose boundary estimates warrant refinement.
- C. Confidence-Based Boundary Refinement: Segments satisfying Fj ≥ FT receive updated probabilities incorporating APP information from the preceding computation.The threshold FT lies in [0, 1].
- C. Confidence-Based Boundary Refinement: The decoder repeats segmentation and APP computation with updated transition probabilities while retaining the original shortlisted candidates.If a segment’s confidence increases, its APPs are updated; otherwise, the initial APPs are retained.
D. Computational Complexity
MDC decoding is parallelizable across reads and segments, with complexity linear in the number of reads and segments but exponential in the message-substring length through the 4^k̃ term. Keeping k̃ small preserves practicality but increases marker redundancy.
- D. Computational Complexity: The MDC decoder has total complexity O(tνΦ^2 + tνB^4k̃ + tνB^2L) and parallel time complexity O(νΦ^2 + tB^4k̃ + tB^2L).Here Φ is the offset limit, B the segment length, and L the shortlist size.
- D. Computational Complexity: Segmentation costs O(tνΦ^2) across t reads and parallelizes across reads to O(νΦ^2).The offset search considers at most (2Φ)^2 pairs at each of ν segment boundaries.
- D. Computational Complexity: APP computation shortlists candidates using Jaccard similarity over the full codebook before calculating posterior probabilities over the shortlist.For fixed κ, comparing vectors of length B requires O(B) time per codeword.
- D. Computational Complexity: Boundary refinement does not change the overall complexity order because its segmentation and APP terms already occur in the initial decoder.Its total complexity is O(tνΦ^2+tνB^2L), with parallel time O(νΦ^2 + tB^2L).
- D. Computational Complexity: The complexity is linear in t and ν but exponential in k̃ through 4^k̃.Choosing k̃ < 10 can keep computation practical, at the expense of more segments and marker redundancy.
V. SIMULATION RESULTS
The simulations evaluate MDC as an inner code and within an outer-LDPC concatenation under a 10% edit-error channel. MDC improves inner-code reliability and decoding time, while its concatenated-code gains are strongest at higher overall rates.
- V. SIMULATION RESULTS: The evaluation measures inner-code quaternary symbol error rate and concatenated-code frame error rate after LDPC belief-propagation decoding.The inner SER uses hard decisions on MDC-generated APPs, while the concatenated FER follows outer LDPC decoding.
- V. SIMULATION RESULTS: The channel uses pe = 10% with edit proportions (ps, pd, pi) = (0.527, 0.447, 0.026)pe, matching empirical DNA-storage measurements.The 10% total edit rate represents a high-error regime associated with low-fidelity synthesis or nanopore sequencing.
- V. SIMULATION RESULTS: Inner-code comparisons use CC, MR, and MDC with common blocklength n = 160 at rates R = 0.7 and R = 0.8.The CC is punctured from a rate-0.5 construction, while MR repeats symbols once with uniformly spaced periods.
- V. SIMULATION RESULTS: For R = 0.7 and R = 0.8, MDC achieves lower SER than CC and MR for t ≥ 3, with larger improvements as reads increase.The MDC decoder also decodes faster than the alternatives for R = 0.8, reaching 34 ms per n = 160 codeword at t = 8 with parallelization.
- V. SIMULATION RESULTS: In concatenated schemes, MDC and CC are paired with outer LDPC codes decoded by belief propagation for 100 iterations.The CC-LDPC construction uses TBMA for inner-code decoding to produce more accurate APPs.
- V. SIMULATION RESULTS: At overall rate 0.5 MDC matches CC approximately, while at rates 0.6 and 0.7 MDC-based constructions provide significant FER gains.These higher-rate settings are described as more representative of cost-efficient practical DNA storage.
- V. SIMULATION RESULTS: MDC-based constructions are suited to multi-read edit channels in the short-blocklength, high-rate regime while maintaining practical decoding complexity.The conclusion connects reliability at medium-to-high overall rates with efficient use of DNA synthesis and sequencing resources.