New Pangenome Index Cuts Storage Elevenfold While Supporting Variable Substring Queries

A computational research team has introduced Maximal Exact Match Ordered, an algorithmic pangenome indexing framework that allows arbitrary-length sequence queries across collections of genomes while drastically reducing memory and storage footprints compared to conventional substring indexes. Described in Algorithms for Molecular Biology, the method replaces traditional fixed-length substring catalogs with compressed records of maximal exact matches identified between an anchor sequence and a multi-genome collection. When tested against standard bioinformatics tools across eighty-nine human autosomal haplotypes, the resulting index occupied roughly two gigabytes of storage space, demonstrating an eleven-fold size reduction relative to PanKmer and nearly a nine-fold reduction compared to a consolidated KMC3 database. Because the index decouples search capabilities from fixed substring dimensions, researchers can examine sequence conservation and presence across variable window resolutions without reconstructing auxiliary data structures. This development offers a scalable mathematical mechanism for exploring large pangenomic datasets generated by modern sequencing technologies.

The rapid proliferation of high-quality long-read assemblies has expanded biological reference sets into expansive pangenomic cohorts, including human, vertebrate, and plant resources such as the Human Pangenome Reference Consortium, the Vertebrate Genomes Project, and multi-lineage Arabidopsis thaliana catalogs. These assemblies allow investigators to characterize complex structural variations, observe single-copy genes, and trace sequence conservation across diverse populations. However, standard analytical pipelines encounter severe computational bottlenecks when scaling to dozens or hundreds of distinct genomes. Graph-based pangenome indexing strategies require computationally demanding multiple sequence alignment steps that often necessitate masking complex repetitive segments, such as designated dna-brnn regions, thereby omitting biologically meaningful variation. Conversely, methods relying on de Bruijn graphs and k-mer tables require setting a fixed substring length during initial database creation. For example, the PanKmer system is restricted to evaluating substrings of length thirty-one, while a separate KMC3 database built for each individual haplotype across the Human Pangenome Reference Consortium dataset requires 1.26 terabytes of disk capacity.

To overcome these structural limitations, the authors developed MEMO by adapting the concept of sequence landscapes, which characterize the lengths of half-maximal exact matches between a query sequence and a reference text. In formal string terminology, these matches correspond to matching statistics vectors that record the longest exact suffix occurring in a target sequence at every coordinate. By evaluating the mathematical behavior of consecutive matching statistics values, the authors proved that adjacent offsets exhibit a strict sawtooth property wherein successive lengths cannot increase by more than one character. The local peaks of these sawtooth trajectories define maximal exact matches, representing exact sequence intervals that cannot be extended in either direction without encountering a mismatch or terminating at a string boundary. Instead of indexing all possible fixed substrings across every genome, MEMO establishes a designated anchor genome within the pangenome, termed the pivot, and computes matching statistics vectors between this pivot and every other assembled genome using the external sequence tool MONI.

The indexing architecture leverages a key mathematical observation regarding coordinate overlaps between adjacent matches to verify substring membership. A substring originating from the pivot sequence is present in another target genome if and only if its genomic interval is completely enclosed within an indexed maximal exact match. However, the researchers discovered that storing full match intervals generates unnecessary data redundancy. Instead, MEMO computes and stores only overlapping intervals formed between consecutive maximal exact matches, referred to as overlap-MEMs. Under the proven presence-absence logic, a query substring is absent from a target genome if it spans an overlap-MEM interval with overhangs extending beyond both the start and end coordinates. If the interval between two consecutive matches is adjoining, sharing an identical termination and starting coordinate, it is recorded as a single-point genomic boundary. This formulation guarantees that testing whether a substring covers an overlap-MEM yields an exact presence-absence determination across all genomes without storing exhaustive substring inventories.

To quantify sequence conservation across the pangenome rather than merely checking binary membership, the authors structured matching statistics into order-based hierarchies. In this formulation, matching statistics calculated between the pivot and remaining assemblies are sorted along each column in descending order, producing an order-matching-statistics matrix. The authors proved mathematically that the resulting rows preserve a sawtooth property analogous to individual sequences, ensuring bounded coordinate variation. Peaks extracted from this sorted matrix form order-MEMs, which represent maximal exact matches ranked across genome depth rather than mapped to specific genome identifiers. A query substring contained within an order-MEM at index position i is guaranteed to occur in at least that number of other genomes across the pangenome. By indexing overlaps between consecutive order-MEMs annotated by their rank, MEMO computes exact conservation counts. Furthermore, because lower-order intervals nest hierarchically within higher orders, search algorithms can perform early stopping, terminating query traversal immediately once a substring is confirmed absent from higher-order tiers.

Building upon this hierarchical design, the study introduced two lossy compression techniques that dramatically shrink index footprints when investigators do not require absolute single-genome counting precision. The first approach, termed quantile sampling, retains only matrix rows that correspond to preselected cohort fractions. For instance, in an eighty-nine haplotype human dataset, the authors sampled rows eight, seventeen, twenty-six, and continuing upwards to eighty-nine, retaining boundary transitions for successive ten-percent increments while discarding all intermediate rows. This produces a decile-resolution conservation index reporting whether a sequence appears in at least ten, twenty, or up to one hundred percent of assemblies. The second strategy applies interval-length filtering by restricting query lengths to a predefined threshold. Because a query substring of length k cannot be absent due to an overlap-MEM exceeding length k minus two, developers can discard large overlap intervals when queries are restricted to lengths below thirty-one. By removing non-essential long intervals, storage requirements shrink substantially while maintaining complete query accuracy.

To store these genomic intervals efficiently, the researchers engineered a columnar storage pipeline utilizing Apache Parquet through the PyArrow library. Conventional genomic interval data are customarily recorded in flat text Browser Extensible Data files, which exhibit poor compression efficiency when handled with standard row-based compression utilities like gzip or tabix. Under MEMO, coordinate tables are segmented into half-gigabyte blocks and compressed using the Zstandard codec. Because columnar layouts group identical contig labels and monotonically ordered numerical coordinates within adjacent memory blocks, the Zstandard algorithm exploits repeating patterns far more effectively than row-major compression formats. In empirical benchmarks evaluating identical interval sets, Parquet compression with Zstandard achieved approximately forty-fold data compression, delivering index files roughly four times smaller than those produced by bgzip paired with tabix. Storing overlap intervals across all genomes in a unified file further outperformed separate per-genome archives, confirming that columnar data organization is critical for compact pangenome indexes.

Experimental evaluations on eighty-nine human autosomal haplotypes, encompassing eighty-eight assemblies from the Human Pangenome Reference Consortium alongside the complete T2T-CHM13 assembly, demonstrated remarkable storage reductions. While the uncompressed input FASTA sequences totaled 254.46 gigabytes, the lossless MEMO membership index occupied only 2.04 gigabytes, achieving a 539.2-fold reduction compared to a KMC3 membership database. For conservation queries, the full MEMO index was 11.4 times smaller than PanKmer and 8.8 times smaller than the combined KMC3 conservation database. Applying decile sampling compressed the conservation index to 0.87 gigabytes. When decile sampling was paired with interval filtering restricting queries to lengths of thirty-one or fewer, the total index size shrank to 0.66 gigabytes. Replicating the evaluations using the GRCh38 assembly as the pivot yielded comparable storage metrics. Across scaling experiments expanding from nine to eighty-nine haplotypes, MEMO index sizes increased 6.5-fold, maintaining a trajectory projected to remain well below four gigabytes as additional human genomes are incorporated.

Query execution speeds and memory profiles also showed substantial improvements during benchmark testing on the human leukocyte antigen locus, a highly polymorphic 3.75-megabase region on chromosome six. Evaluating thirty-one-mer conservation across this locus required 13.89 seconds with MEMO, executing 2.6 times faster than KMC3 and 365.3 times faster than PanKmer, while consuming less than half the peak memory of competing tools. The membership search executed 107.2 times faster than KMC3 while utilizing over five-fold less memory. In sequence visualization experiments modeled after Panagram, conservation profiles generated by MEMO accurately captured known areas of elevated single-nucleotide polymorphism density. Zooming into the complex HLA delta block confirmed that decile-approximated profiles were virtually indistinguishable from full-fidelity outputs, verifying that lossy compression preserves key biological insights. In vertebrate evaluations across sixteen genomes from the Vertebrate Genomes Project totaling 26.80 gigabytes, anchored to the blenny genome, MEMO scaled 3.8-fold, demonstrating stable multi-species performance where k-mer tables struggle with high sequence divergence.

Despite these analytical advantages, the authors emphasized key methodological boundaries and trade-offs inherent to the current implementation. A central architectural limitation is the strict reliance on a single pivot sequence chosen during index construction, which restricts sequence queries exclusively to substrings contained within that designated reference. While high-quality assemblies such as T2T-CHM13 provide natural anchors for human datasets, diverse multi-species cohorts lacking an obvious reference standard may require constructing multiple independent pivot indexes. In addition, initial index construction remains computationally demanding; building MONI indexes and performing pairwise matching statistics queries consumed considerable time and memory compared to fast counting tools like KMC. The authors noted that distributing MONI computations in parallel mitigates construction times, and future implementations could replace MONI with specialized data structures such as profile document arrays. Nevertheless, MEMO establishes that maximal exact match indexing paired with columnar compression offers a highly compact, flexible paradigm for exploratory pangenomic analysis across arbitrary substring lengths.

Subject of Research: Algorithmic indexing of pangenomes using maximal exact matches for variable-length sequence queries

Article Title: Mem-based pangenome indexing for k-mer queries

Article References: Hwang, S., Brown, N. K., Ahmed, O. Y., Jenike, K. M., Kovaka, S., Schatz, M. C., & Langmead, B. (2025). Mem-based pangenome indexing for k-mer queries. Algorithms for Molecular Biology, 20(1), Article 3. https://doi.org/10.1186/s13015-025-00272-y

Image Credits: AI Generated

DOI: 10.1186/s13015-025-00272-y

Keywords: pangenomics, maximal exact matches, matching statistics, k-mer queries, MEMO, Apache Parquet, columnar compression, Human Pangenome Reference Consortium, T2T-CHM13, sequence conservation, HLA locus, Vertebrate Genomes Project, de Bruijn graphs, bioinformatics algorithms, sequence landscapes, quantile sampling, MONI