Adaptive Tracepoints for Pangenome Alignment Compression

Abstract

MotivationStoring millions of sequence alignments from large-scale genomic comparisons requires efficient compression methods. While fixed-size alignment encodings offer uniform spacing and bounded reconstruction cost, they cannot adapt to variable alignment complexity across sequences, missing compression opportunities in conserved regions. ResultsWe 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.7x better compression than fixed-length encodings (l=100) 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-139x relative to uncompressed representations, with no score degradation and reconstruction time linear in alignment length. AvailabilityCode and documentation are publicly available at https://github.com/AndreaGuarracino/tracepoints, https://github.com/AndreaGuarracino/tpa, and https://github.com/AndreaGuarracino/cigzip. Contactaguarracino@tgen.org Supplementary informationSupplementary data are available at Bioinformatics online.