Source-linked AI summary
Fundamental Limits of Sequence Reconstruction Problems in Immunogenomics
Jaswanthi Mandalapu, Deepak Charan, V. Arvind Rameshwar, Nir Weinberger
TL;DR
How many independently generated traces suffice to reconstruct an underlying sequence with prescribed error, when D-gene observations are differently corrupted and the models’ fundamental complexities remain open? The paper derives information-theoretic lower bounds and analyzes low-complexity reconstruction algorithms for three trimming-and-extension channels. Trace complexity Tδ(n) is Θ(n) for TrimSuffixAndExtend and Θ(n²) for TrimAndExtend.
Problem
How many independently generated traces suffice to reconstruct an underlying sequence with prescribed error, when D-gene observations are differently corrupted and the models’ fundamental complexities remain open?
Source: §I · p. 1Method
The paper derives information-theoretic lower bounds and analyzes low-complexity reconstruction algorithms for three trimming-and-extension channels.
Source: §II · p. 3, §III · p. 3Results
Trace complexity Tδ(n) is Θ(n) for TrimSuffixAndExtend and Θ(n²) for TrimAndExtend.
Source: B. Our Contributions · p. 2Takeaways & Limitations
Low-complexity algorithms attain the lower-bound scaling for the first two channels, whereas the third channel’s precise trace complexity remains unresolved.
Source: §II · p. 3, §V · p. 7For SuffixExtend-t(TrimSuffix), a gap between asymptotic trace-complexity bounds remains; mutation or substitution noise is left for future analysis.
Source: §V · p. 7
Abstract
from arXiv · showhide
The goal of personalized immunogenomics is to recover an individual's germline immunoglobulin gene segments from 'repertoire sequences' altered by trimming, extension, and mutation. In this work, we study the fundamental trace complexity (or the number of samples/traces required for accurate reconstruction) of D-gene reconstruction under three biologically motivated trace-generation models introduced by Bhardwaj et al. (2021) and develop practical algorithms for reconstruction problems left open in the original work. First, for the TrimSuffixAndExtend model, we establish the optimal trace complexity to be {\Theta(n)}, and develop a low-complexity Prefix-Filtered Mode (PFM) decoder that achieves this scaling. Second, for the closely related two-sided TrimAndExtend model, we show that the optimal trace complexity is instead {\Theta(n^2)}, and is achieved by the simple Bit-Wise Mode (BWM) decoder. Third, for the SuffixExtend-t(TrimSuffix) model, we establish polynomially separated lower and upper bounds on trace complexity. Our results follow from information-theoretic lower bounds coupled with tight analyses of the proposed reconstruction algorithms.
I. INTRODUCTION
The paper frames D-gene recovery as reconstructing an underlying sequence from repertoire sequences altered by biological trimming and extension. It asks how many independently generated traces are needed for reliable recovery, a question left open for the considered models.
I. INTRODUCTION
- AIRR-seq provides collections of antibody sequences assembled from V, D, and J germline segments, but not the underlying gene segments themselves.Reconstructing those segments is a key inference problem in repertoire analysis,.Source: §I · p. 1
- Incomplete reference databases, immunoglobulin-locus polymorphism, and individuals carrying only a subset of catalogued alleles further challenge reconstruction.Source: §I · p. 1
- D segments are short, trimmed at both ends, and surrounded by nontemplated nucleotides, so the underlying sequence appears only through partial, differently corrupted versions.The paper identifies specialized approaches such as IgScout and MINING-D, while noting that fundamental trace complexities and matching algorithms remained largely open.Source: §I · p. 1
- Trace complexity is the minimum number of independently generated traces needed to reconstruct the sequence with a prescribed error probability.Source: §I · p. 1
A. Relevant Literature
Sequence reconstruction has been studied across several information-theoretic and applied settings. These trimming models additionally create dependent coordinate errors that can themselves inform reconstruction.
A. Relevant Literature
- Related work studies recovery from corrupted observations in sparse estimation and latent-structure learning,, exact structure recovery, and deletion-channel trace reconstruction –.Source: A. Relevant Literature · p. 1
- Other related areas include combining memoryless-channel traces – and DNA-storage systems, alongside information-theoretic work on their storage and reconstruction limits –.Source: A. Relevant Literature · p. 2
- Unlike many existing settings, trimming causes contiguous, non-independent coordinate errors, and information from one trace portion can reveal the reliability of later coordinates.The paper says this dependence leads to markedly different trace-complexity scaling across models.Source: A. Relevant Literature · p. 2
B. Our Contributions
The paper derives information-theoretic lower bounds and develops low-complexity algorithms for three biologically motivated channels. It establishes tight complexities for two models and separated bounds for the third.
B. Our Contributions
- The lower bounds address all three models introduced by.Source: B. Our Contributions · p. 2
- For TrimSuffixAndExtend (W1), trace complexity is Θ(n), achieved by Prefix-Filtered Mode (PFM) using the nested prefix structure.Bit-Wise Mode (BWM) instead requires O(n^2 log n) traces.Source: B. Our Contributions · p. 2
- For TrimAndExtend (W2), trace complexity is Θ(n^2), and the simple BWM decoder achieves this optimal scaling.Despite closely related corruption mechanisms, W1 and W2 have different trace-complexity scalings.Source: B. Our Contributions · p. 2
- For SuffixExtend-t(TrimSuffix) (W3), the paper proves an Ω(n) lower bound and gives an O(n^3) algorithmic upper bound, leaving the exact complexity open.Source: B. Our Contributions · p. 2
II. CHANNEL MODELS AND PRELIMINARIES
The paper models D-gene reconstruction using three trimming-and-extension channels and defines the trace-complexity framework. It combines information-theoretic lower bounds with low-complexity reconstruction procedures.
II. CHANNEL MODELS AND PRELIMINARIES
- The three channels respectively replace a uniformly selected suffix, replace prefixes and suffixes with total trimmed length at most n, or delete a suffix and append a bounded random extension.The models are W1, W2, and W3; the paper attributes their introduction to.Source: §II · p. 2
- A reconstruction algorithm takes independently generated traces as input and returns an estimated length-n gene sequence.Source: §II · p. 2
- The channel trace complexity uses the MAP decoder, which minimizes average error probability; the paper also defines trace complexity conditioned on a fixed input.For W1–W3, trace complexity is independent of the transmitted sequence.Source: §II · p. 3
- For W1 and W2, lower bounds use Fano’s method and KL divergence; W3 uses a binary hypothesis test based on total variation distance.The lower-bound framework reduces W1 and W2 to estimating a single input coordinate.Source: §II · p. 3
- The proposed low-complexity algorithms match the lower bounds up to constants for W1 and W2, while MAP decoding requires time exponential in n.For W3, the paper obtains bounds but not a tight characterization.Source: §II · p. 3
III. TRIMSUFFIXANDEXTEND (CHANNEL W1)
For W1, the section establishes optimal linear trace complexity with Prefix-Filtered Mode (PFM), contrasting it with the more costly coordinate-wise Bit-Wise Mode (BWM).
III. TRIMSUFFIXANDEXTEND (CHANNEL W1)
- O(n^2 log n) traces suffice for coordinate-wise BWM on W1, whose complexity is governed by the last coordinate's preservation probability of 1/(n+1).Under W1, preservation probability decreases with position.Source: §III · p. 4
- PFM filters traces that match the reconstructed prefix, then uses the mode of their next-coordinate symbols, exploiting coordinate structure instead of estimating positions independently.This prefix-based dependence addresses the suboptimality of treating coordinates independently.Source: §III · p. 4
- Among traces matching the reconstructed prefix, the correct next symbol has a constant advantage; Hoeffding bounds per-step errors, which are combined across coordinates.The proof outline uses the filtered trace set and controls the overall failure probability across positions.Source: §III · p. 4
- Θ(n) traces are necessary and sufficient for W1, and PFM achieves this order-optimal trace complexity.The lower bound is Ω(n), while PFM reconstructs using O(n) traces.Source: §III · pp. 3–5
A. Empirical Evaluation
The evaluation uses Monte Carlo trials to estimate the traces needed to meet target error rates over W1. PFM needs fewer traces than BWM, with the advantage widening as sequence length grows and persisting across tested error targets.
A. Empirical Evaluation
- Monte Carlo trials estimate reconstruction error for uniformly random binary sequences passed independently through W1, with Wilson confidence intervals used to set conservative and optimistic trace thresholds.The central threshold is the first trace count where the empirical error estimate falls below δ.Source: A. Empirical Evaluation · p. 5
- PFM requires far fewer traces than BWM over W1, and the gap widens with sequence length.The plots are visually consistent with BWM's O(n^2 log n) guarantee and PFM's order-optimal O(n) guarantee.Source: A. Empirical Evaluation · p. 5, Figure 1 · p. 6
- For n = 20, required traces decrease sharply as δ rises from 0.01 toward 0.1, then flatten for larger δ; PFM retains a substantial, uniform advantage over BWM throughout the tested range.Source: Figure 2 · p. 6, A. Empirical Evaluation · p. 6
IV. TRIMANDEXTEND (CHANNEL W2)
For channel W2, the paper establishes a tight Θ(n^2) trace-complexity bound, attained by BWM. Its coordinate-wise estimates are sufficient because the least reliable coordinates are the sequence boundaries.
IV. TRIMANDEXTEND (CHANNEL W2)
- Tδ(n) = Θ(n^2) for W2, and BWM achieves order-optimal trace complexity.The lower bound is Ω(n^2), while BWM reconstructs with probability at least 1 − δ using O(n^2) traces.Source: §IV · p. 6
- The least reliable W2 coordinates are the boundaries, each uncorrupted with probability Θ(1/n), so reliable coordinate-wise recovery requires Θ(n^2) traces.The coordinate reliability profile is symmetric about the sequence midpoint.Source: §IV · p. 6
- BWM's O(n^2) upper bound matches the information-theoretic Ω(n^2) lower bound, unlike W1, where coordinate-wise BWM is suboptimal.For W1, the least reliable coordinate is biased toward one end; for W2, coordinate-wise estimation reaches the information-theoretic limit.Source: §IV · p. 6
A. Empirical Evaluation
The W2 experiments compare BWM and PFM using Monte Carlo evaluation across sequence lengths and target error probabilities. BWM modestly outperforms PFM across the tested sequence lengths and requires fewer traces throughout the displayed error-probability range.
A. Empirical Evaluation
- The W2 experiments use the Monte Carlo procedure and confidence-interval thresholds described for the preceding evaluation.Source: A. Empirical Evaluation · p. 6
- BWM modestly outperforms PFM over the tested W2 sequence lengths.The comparison fixes δ = 0.01 and varies n; the result agrees with BWM's order-optimal O(n^2) trace complexity.Source: Figure 3 · p. 6, A. Empirical Evaluation · p. 6
- For W2, BWM requires fewer traces than PFM throughout the displayed target-error range.With n = 20, required traces decrease rapidly for small δ and then flatten as the target error probability is relaxed.Source: Figure 4 · p. 7, A. Empirical Evaluation · p. 7
V. SUFFIXEXTENDt(TRIMSUFFIX) (CHANNEL W3)
For W3, TrimAndFindMode reconstructs the input using O(n^3) traces, while the available asymptotic bounds leave its precise trace complexity open. The accompanying proof excerpts also analyze error bounds for mode decoding and trimming channels.
V. SUFFIXEXTENDt(TRIMSUFFIX) (CHANNEL W3)
- O(n^3) traces suffice for TrimAndFindMode on W3, but the gap between its asymptotic bounds remains open.The algorithm uses longest-common-prefix lengths; the paper also identifies mutation/substitution noise as a direction for future work.Source: §V · p. 7
A. Proof of Lemma 2
- The proof relates MAP decoding error to a Fano and pairwise-KL bound, using the fact that conditional error is identical for every transmitted sequence.Source: A. Proof of Lemma 2 · pp. 8–9
B. Proof of Theorem 1
- The W1 lower-bound proof compares the all-zero input with an input differing only at the final coordinate, then uses the resulting KL bound.Source: B. Proof of Theorem 1 · p. 9
C. Proof of Theorem 2
- For W1, the coordinate-wise error analysis applies Hoeffding’s inequality and a union bound over coordinates to ensure total error at most δ.Source: C. Proof of Theorem 2 · pp. 9–10
D. Proof of Lemma 3
- In Lemma 3’s event, a trimmed prefix position must be replaced by zero; all replaced positions must independently receive zero.Source: D. Proof of Lemma 3 · p. 10
VI. PROOF OF THEOREM 4
- For W2, the terminal-coordinate inputs differ in their output distributions only when the last input symbol survives trimming.Source: §VI · p. 10
A. Proof of Lemma 4
- For Lemma 4, an uncorrupted position k+1 guarantees that the trace agrees with the true prefix of length k.Source: A. Proof of Lemma 4 · pp. 10–11
B. Proof of Lemma 5
- Lemma 5 bounds incorrect-symbol mode errors among traces in S_k with Hoeffding’s inequality, then takes a union bound over incorrect symbols.Source: B. Proof of Lemma 5 · p. 11
C. Proof of Theorem 5
Theorem 5 bounds W2’s trace complexity under BWM by O(n^2). Its proof analyzes coordinate-wise symbol errors; the accompanying lemma excerpts state additional claims about output lengths.
C. Proof of Theorem 5
- Under W2, coordinate j is uncorrupted exactly when R1 ≤ j−1 and R2 ≤ n−j, giving the per-coordinate basis for the BWM error analysis.Source: C. Proof of Theorem 5 · p. 11
- O(n^2) traces suffice for W2 under BWM, and therefore the channel’s trace complexity is O(n^2).Source: C. Proof of Theorem 5 · p. 12
VII. PROOF OF LEMMA 8
- The stated maximum over nonzero strings is attained by strings whose length is n−1.Source: §VII · p. 12
A. Proof of Theorem 7
Theorem 7’s proof uses total-variation separation between W3 output distributions to obtain a trace-complexity lower bound. The analysis evaluates this separation using a particular input string.
A. Proof of Theorem 7
- The proof bounds W3’s minimum total-variation separation using the input 0^(n−1)1.Source: A. Proof of Theorem 7 · p. 12
- For the selected input, d_n(W3) ≤ 1/[2(n+1)(t+1)].Source: A. Proof of Theorem 7 · p. 12
- Applying Lemma 9 converts the separation bound into a trace-complexity lower bound.Source: A. Proof of Theorem 7 · p. 12