Limits on reconstructing immune gene sequences from altered samples
Fundamental Limits of Sequence Reconstruction Problems in Immunogenomics
Information Theory
Summary
Reconstructing a person's immune gene segments accurately is challenging because the recorded sequences are often trimmed, extended, or mutated. The authors studied three realistic biological models describing how these immune gene sequences get altered and determined the minimum number of samples needed to recover the original sequences reliably. They also introduced algorithms that match these theoretical limits, meaning their methods use about as few samples as possible. These results help understand what is fundamentally possible in identifying immune genes from messy data.
What this means in practice
- •For bioinformatics engineers: Design gene reconstruction tools knowing the minimum sample sizes for immune gene recovery under realistic conditions.
- •For clinical genomics teams: Plan data collection protocols with optimal sample counts to reconstruct patients’ immune genes from partial or altered sequences accurately.
A theory result. No direct application yet.
Authors
Jaswanthi Mandalapu, Deepak Charan, V. Arvind Rameshwar, Nir Weinberger
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.