パンゲノムアラインメント圧縮のための適応型トレースポイント

Storing 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.

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 ( 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-139 × relative to uncompressed representations, with no score degradation and reconstruction time linear in alignment length.

Code and documentation are publicly available at https://github.com/AndreaGuarracino/tracepoints , https://github.com/AndreaGuarracino/tpa , and https://github.com/AndreaGuarracino/cigzip .

aguarracino@tgen.org.

Supplementary data are available at Bioinformatics online.