Tag arrays bring lossless indexing to large human pangenome graphs

A team at the University of California, Santa Cruz has unveiled the first practical implementation of tag array indexing for pangenome graphs, a data structure that promises to make lossless, haplotype-aware search over massive collections of human genomes both feasible and efficient. The work, published in Algorithms for Molecular Biology by Parsa Eskandar, Benedict Paten and Jouni Sirén, addresses one of the central computational bottlenecks in modern genomics: how to index thousands of genome sequences at once without discarding information or drowning in redundant results.

Linear reference genomes have long served as the coordinate framework for genomics, but they capture only a single version of the genome. In regions with complex structural variation or high diversity, a linear reference may exclude certain sequences entirely, and reads from divergent haplotypes can align poorly or not at all, producing a systematic distortion known as reference bias. Pangenome graphs were developed to counter this problem by embedding multiple haplotypes and structural variants into a shared graph, where nodes represent sequences and edges capture possible continuations along different haplotypes. Large-scale efforts such as the Human Pangenome Reference Consortium (HPRC) and the African pangenome project have adopted these graph-based representations to better characterize genomic variation across populations.

Indexes that map query sequences to matching positions in a reference are the engine of sequence alignment. In the standard seed-and-extend strategy, the index first identifies short exact matches, or seeds, between the query and the reference; these seeds are then filtered and chained to sketch the alignment, which is refined with dynamic programming. But existing pangenome indexes each carry limitations. FM-indexes built directly on haplotype sequences have been constructed efficiently for collections of hundreds of human haplotypes, yet they report the same seed separately for every haplotype in which it appears, and aligners prefer informative seeds with minimal redundancy. FM-indexes built directly on pangenome graphs do merge equivalent seeds, but when the graph is not similar to a de Bruijn graph, their construction requires expensive graph transformations that can be lossy, meaning parts of the haplotypes go missing from the index, and the process is fragile enough that a suitable transformation cannot always be found. Sparse minimizer indexes, favored in recent aligners, build quickly and avoid redundant seeds, but the seed length must be fixed in advance, forcing a trade-off between sensitivity and specificity that FM-indexes do not require.

The new method builds on a theoretical idea proposed in earlier work: the tag array. The Burrows-Wheeler transform (BWT), the foundation of the FM-index, is built by sorting the suffixes of the sequences lexicographically and listing the characters preceding each suffix in that order. When sequences are similar, characters preceding similar suffixes tend to be identical, so the BWT contains long runs of identical characters and compresses well. By the same logic, if a pangenome graph is a reasonable alignment of similar sequences, the graph positions corresponding to similar suffixes are likely the same, so a tag array listing the graph position for each suffix in lexicographic order should also be highly compressible. Given a lexicographic interval from an FM-index of the haplotypes, document listing techniques over the tag array can enumerate the graph positions matching the pattern. A related recent effort by Olbrich and Ohlebusch computed TAG arrays over multiple sequence alignments rather than sequence graphs, reflecting growing interest in these structures, but the new paper delivers the first practical implementation for pangenome graphs.

The construction pipeline is deliberately layered to keep memory in check. Naive approaches, such as traversing every haplotype or assigning tags in text order and permuting with the suffix array, would require storing enormous arrays in memory. Instead, the method first uses unique k-mers, substrings of length k with exactly one starting position in the graph, as anchors: because they are unique, every occurrence in the BWT must correspond to the same graph position, so each unique k-mer directly yields a run of identical tags. The r-index, which stores suffix array samples at run boundaries of the run-length encoded BWT and scales with the number of runs rather than text length, locates these k-mers efficiently. The anchors are then extended backward through the graph wherever the extension remains unique, including through predecessor branches where a character is contributed by exactly one predecessor node. Finally, a haplotype traversal stage walks each haplotype backward through the BWT and fills in any remaining untagged positions, guaranteeing that the entire BWT is labeled.

Managing these runs efficiently required a new data structure: a Run-Length B+ Tree, or RLB+, which stores each run as a key, a start position and an implicitly derived length, and merges adjacent runs sharing the same graph position during insertion. Because bidirectional merges can shrink leaf nodes below the minimum key threshold, the tree implements a rebalancing mechanism that borrows keys from siblings or merges leaves while preserving logarithmic insertion and query time. To scale to whole genomes, the team constructs tag arrays independently per chromosome and then merges them into a single global index using an interleaving array computed on the fly from a whole-genome r-index, with the graph topology in GBZ format providing the mapping from sequence numbers to chromosomes through weakly connected components.

The evaluation used two human pangenome graphs from the HPRC, including the v2 graph with 464 haplotypes, on a cluster node with 256 logical CPUs and 2.0 TiB of RAM. On average, 95.1 percent of BWT positions in the v1.1 graph and 94.1 percent in the v2 graph were already covered after the first two construction stages, unique k-mer anchoring and graph-based extension, with coverage highest in autosomes such as chr1 through chr8 and comparatively lower in chrX and chrY, where fewer phased samples and higher sequence redundancy prevail. Because the expensive final haplotype traversal stage must handle only the remaining few percent, memory usage and construction time drop substantially. The maximum resident set size over the whole pipeline was 128 GiB for the v1.1 graph and 519 GiB for the v2 graph, and the maximum per-chromosome build time, including BWT construction, was 6.7 hours for v1.1 and 26.5 hours for v2, with the whole-genome r-index and merging steps adding further hours on top.

Compression results underline why the approach scales. Although the total base content of the v2 graph is roughly five times larger than the v1.1 CHM13 graph due to the hundreds of additional haplotypes, the number of BWT runs increased only about 1.2-fold on average and the number of tag runs about 2-fold, showing that shared paths across individuals are coalesced into longer runs. Average tag run lengths in the v2 graph reached 375, reflecting both increased redundancy from shared haplotypes and cleaner, more contiguous assemblies. Query benchmarks over 10,000 k-mers of varying lengths showed total query time highest for small k-mers, where large BWT intervals force many unique tag lookups, fastest around k=50, and gradually rising again for long patterns as r-index LF-mapping steps accumulate. For coordinate translation, a new capability that maps any interval on one haplotype to all other haplotypes passing through the same graph positions, the find-tags phase processed an average of 234,152 base pairs per second on the v2 graph for 10,000-base intervals, while the find-sequences phase processed an average of 188 tags per second across all interval lengths.

The bidirectional variant of the index, built as an FMD-index over both forward and reverse strands, supports maximal exact match (MEM) finding, a key seeding step for read mapping. Benchmarked against ropebwt3, a highly optimized FM/FMD-index tool, the new index was slower at MEM finding, using roughly 1.6 to 1.8 times the time ropebwt3 needs for indexing the HPRC haplotypes, but the authors note that the tag query mechanism is modular and can be attached to any MEM-finding backend, and that chromosome-level parallelism can cut wall-clock construction time by more than half in ways an incremental approach cannot. Because no other lossless pangenome indexes exist for direct comparison, the evaluation focused on MEM-finding functionality. The authors also point out that while construction is memory intensive, at roughly 500 GiB for the v2 bidirectional index, it needs to be done only once per graph, and the final index requires about 149 GiB; the construction cost is also lower than that of building the graphs themselves with the Minigraph-Cactus pipeline.

Beyond pattern search, the sampled tag arrays, which store only tag runs at graph node boundaries and occupy 10 to 15 percent of the full index, enable one-to-all coordinate translation without relying on a linear reference, letting annotations, variant intervals and structural features be lifted directly across haplotypes and even across different versions of a pangenome graph. The software is implemented in C++ and freely available under the MIT license. The authors identify remaining challenges, including a faster gap-filling algorithm, more efficient tag array compression and optimization of the r-index structure, but the work establishes a practical indexing layer for building scalable aligners and downstream graph-based analysis tools over complex pangenomes.

Subject of Research: Lossless pangenome graph indexing using run-length compressed tag arrays

Article Title: Lossless pangenome indexing using tag arrays

Article References: Eskandar, P., Paten, B., & Sirén, J. (2026). Lossless pangenome indexing using tag arrays. Algorithms for Molecular Biology, 21(1), Article 12. https://doi.org/10.1186/s13015-026-00301-4

Image Credits: AI Generated

DOI: 10.1186/s13015-026-00301-4

Keywords: pangenome, pangenome graph, FM-index, tag array, Burrows-Wheeler transform, r-index, HPRC, haplotypes, sequence alignment, coordinate translation, maximal exact matches, bioinformatics