Adaptive Tracepoints for Pangenome Alignment Compression

We present adaptive tracepoints, a complexity-aware alignment encoding that segments alignments using configurable complexity metrics (edit distance or diagonal distance) rather than fixed intervals. Segments are bounded by either the number of differences or the deviation from the main diagonal, adapting to local alignment characteristics. Reconstruction guarantees that alignments maintain identical or improved alignment scores. We validate the correctness of our method on simulated and real pangenomes with varying lengths and divergences. Diagonal-bounded tracepoints achieve 10.5-13.7× better compression than fixed-length encodings ( <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>l</mml:mi> <mml:mo>=</mml:mo> <mml:mn>100</mml:mn></mml:math> ) on simulated long sequence alignments (100 Kb), while edit-bounded tracepoints provide a tunable trade-off between compression and reconstruction cost, approaching diagonal-bounded compression at higher thresholds with substantially lower memory and runtime. On real pangenomes (390M alignments), these methods compress alignments by 23-139× relative to uncompressed representations, with no score degradation and reconstruction time linear in alignment length.