Metraipolis › archive › dc_08662684f021

Fundamental Limits of Sequence Reconstruction Problems in Immunogenomics — arXiv:2609.31501

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.31501
License (as archived)
CC0-1.0
Archived
2026-10-08T03:11:30.991Z
SHA-256 of the archived text
95c1ad64e2812afa8a2fdf97e0458f6d866386ed8aa5a01f0e1e6d4b219ba7a0
Stable URL of this page
https://metraipolis.com/documento/dc_08662684f021

How to cite

Fundamental Limits of Sequence Reconstruction Problems in Immunogenomics — arXiv:2609.31501 — arXiv (en), https://arxiv.org/abs/2609.31501 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_08662684f021 (Metraipolis archive dc_08662684f021, sha256 95c1ad64e2812afa8a2fdf97e0458f6d866386ed8aa5a01f0e1e6d4b219ba7a0)
BibTeX
@misc{dc08662684f021,
  title = {Fundamental Limits of Sequence Reconstruction Problems in Immunogenomics — arXiv:2609.31501},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.31501},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_08662684f021; sha256 95c1ad64e2812afa8a2fdf97e0458f6d866386ed8aa5a01f0e1e6d4b219ba7a0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31501. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in math.IT).
Categorie arXiv: Information Theory (cs.IT) ; Signal Processing (eess.SP).
Pagina del lavoro: https://arxiv.org/abs/2609.31501 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T02:45:36.799Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).