Fundamental Limits of Sequence Reconstruction Problems in Immunogenomics
Abstract
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 {Θ(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 {Θ(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.
Related
- The Fundamental Limits of Structure-Agnostic Functional Estimation
- Fundamental limits on photonic state preparation from phase-space majorization
- Data Center Oscillation Isolation and Grid Support: Fundamental Limits and Source-Selective Control
- Fundamental Limits of Quantized MIMO ISAC under Gaussian Signaling
- Fundamental Limits of MIMO ISAC: An Antenna Array Architecture Perspective
BibTeX
@misc{mandalapu2026fundamental,
title = {{Fundamental Limits of Sequence Reconstruction Problems in Immunogenomics}},
author = {Jaswanthi Mandalapu and Deepak Charan and V. Arvind Rameshwar and Nir Weinberger},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.31501},
eprint = {2609.31501},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31501},
}
RIS
TY - UNPB
TI - Fundamental Limits of Sequence Reconstruction Problems in Immunogenomics
AU - Jaswanthi Mandalapu
AU - Deepak Charan
AU - V. Arvind Rameshwar
AU - Nir Weinberger
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.31501
UR - https://arxiv.org/abs/2609.31501
AB - 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 {Θ(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 {Θ(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.
ER -