Human readable compression of GFA paths using grammar-based code

Pangenome graphs offer a compact and comprehensive representation of genomic diversity, improving tasks such as variant calling, genotyping, and other downstream analyses. Although the underlying graph structures scale sublinearly with the number of haplotypes, the widely used GFA file format suffers from rapidly growing file sizes due to the explicit and repetitive encoding of haplotype paths. In this work, we introduce an extension to the GFA format that enables efficient grammar-based compression of haplotype paths while retaining human readability. In addition, grammar-based encoding provides an efficient in-memory data structure that does not require decompression, but conversely improves the runtime of many computational tasks that involve haplotype comparisons.

We present<monospace>sqz</monospace>, a method that makes use of the proposed format extension to encode haplotype paths using byte pair encoding, a grammar-based compression scheme. We evaluate<monospace>sqz</monospace>on recent human pangenome graphs from Heumoset al. and the Human Pangenome Reference Consortium (HPRC), comparing it to existing compressors<monospace>bgzip</monospace>,<monospace>gbz</monospace>, and<monospace>sequitur</monospace>.<monospace>sqz</monospace>scales sublinearly with the number of haplotypes in a pangenome graph and consistently achieves higher compression ratios than<monospace>sequitur</monospace>and up to 5 times better compression than<monospace>bgzip</monospace>in HPRC graphs and up to 10 times in the graph from Heumoset al.. When combined with<monospace>bgzip</monospace>,<monospace>sqz</monospace>matches or excels the compression ratio of<monospace>gbz</monospace>across all our datasets.

These results demonstrate the potential of our proposed extension of the GFA format in reducing haplotype path redundancy and improving storage efficiency for pangenome graphs.