Hub labeling makes exact distance calculation practical for large human pangenome graphs
- 1University of California, Santa Cruz
Abstract
Pangenome graphs are now a standard reference representation, and tools built on them depend on fast minimum-distance queries between graph positions, for example, when clustering seed matches during read alignment. The baseline distance index, previously used by the vg toolkit, answers such queries based on a decomposition of the graph into nested subgraphs called "snarls". Within each snarl, the index uses a dense all-pairs distance matrix. Because such a matrix is quadratic in a snarl's number of children, the large, complex snarls that often occur in many pangenome graphs dominate the overall index size. This means whole-genome graphs can be impractical to index. To mitigate this, the baseline distance index does not fully index the largest snarls, and thus cannot itself answer certain queries involving them. We replace the dense matrix with a hub labeling for snarls above a size limit. Because hub labeling and associated methods are defined for directed graphs, we introduce a directed representation of a snarl's bidirected internal "net graph", whose shortest path lengths are the net graph's minimum walk lengths. Hub labels are built using pruned landmark labeling, ordered by a contraction hierarchy. On four human chromosome pangenomes, our hub-labeling-based distance index indexes every snarl in 0.9 GB to 3.0 GB at a snarl limit of 500, an estimated 28x to 119x less space than dense distance matrices would need for those snarls with more than 500 children, and supports the 3-18.6% of node-to-node queries that the previous index cannot answer by itself. On the queries both indexes can answer, query time distributions broadly overlap. We explore the snarl limit parameter space and are able to build indexes under 50 GB for four human whole-genome pangenomes in under 6 hours, where we estimate dense matrices could have required multiple terabytes.
Related
- Assembly of minimally fragmented metagenomic pangenome graphs
- Somatic structural variation discovery on cancer pangenome graphs
- Structural Variant Aware Identity-by-Descent Detection on Pangenome Graphs
- Pangenome and transcriptome analyses reveal extensive diversity and breeding signatures in the oat GDSL-esterase/lipase gene family
- A Plasmodium falciparum Pangenome Resource to Drive Structural Variant Discovery and to assist Malaria Control
BibTeX
@misc{truong2026labeling,
title = {{Hub labeling makes exact distance calculation practical for large human pangenome graphs}},
author = {Z. Truong and A. Novak and B. Paten},
howpublished = {bioRxiv},
year = {2026},
month = nov,
doi = {10.64898/2026.11.05.764665},
url = {https://www.biorxiv.org/content/10.64898/2026.11.05.764665v1},
note = {CC BY},
}
RIS
TY - UNPB
TI - Hub labeling makes exact distance calculation practical for large human pangenome graphs
AU - Z. Truong
AU - A. Novak
AU - B. Paten
PY - 2026
DA - 2026/11/05
PB - bioRxiv
DO - 10.64898/2026.11.05.764665
UR - https://www.biorxiv.org/content/10.64898/2026.11.05.764665v1
AB - Pangenome graphs are now a standard reference representation, and tools built on them depend on fast minimum-distance queries between graph positions, for example, when clustering seed matches during read alignment. The baseline distance index, previously used by the vg toolkit, answers such queries based on a decomposition of the graph into nested subgraphs called "snarls". Within each snarl, the index uses a dense all-pairs distance matrix. Because such a matrix is quadratic in a snarl's number of children, the large, complex snarls that often occur in many pangenome graphs dominate the overall index size. This means whole-genome graphs can be impractical to index. To mitigate this, the baseline distance index does not fully index the largest snarls, and thus cannot itself answer certain queries involving them. We replace the dense matrix with a hub labeling for snarls above a size limit. Because hub labeling and associated methods are defined for directed graphs, we introduce a directed representation of a snarl's bidirected internal "net graph", whose shortest path lengths are the net graph's minimum walk lengths. Hub labels are built using pruned landmark labeling, ordered by a contraction hierarchy. On four human chromosome pangenomes, our hub-labeling-based distance index indexes every snarl in 0.9 GB to 3.0 GB at a snarl limit of 500, an estimated 28x to 119x less space than dense distance matrices would need for those snarls with more than 500 children, and supports the 3-18.6% of node-to-node queries that the previous index cannot answer by itself. On the queries both indexes can answer, query time distributions broadly overlap. We explore the snarl limit parameter space and are able to build indexes under 50 GB for four human whole-genome pangenomes in under 6 hours, where we estimate dense matrices could have required multiple terabytes.
ER -