Mumemto: efficient maximal matching across pangenomes

Abstract

Aligning genomes into common coordinates is central to pangenome construction, though computationally expensive. Multi-sequence maximal unique matches (multi-MUMs) help to frame and solve the multiple alignment problem. We introduce Mumemto, a tool that computes multi-MUMs and other match types across large pangenomes. Mumemto allows for visualization of synteny, reveals aberrant assemblies and scaffolds, and highlights pangenome conservation and structural variation. Mumemto computes multi-MUMs across 320 human assemblies (960GB) in 25.7 h with 800 GB of memory and hundreds of fungal assemblies in minutes. Mumemto is implemented in C++ and Python and available open-source at https://github.com/vikshiv/mumemto (v1.1.1 at doi.org/10.5281/zenodo.15053447 ).

Fig. 1

Exact match types that Mumemto can compute. Two flags to control how many sequences a match appears in (-k) and how many times a match may appear in any given sequence (-f)

Fig. 2

A, B Comparison of runtime and peak memory usage (measured as maximum resident set size) between multi-MUM finders. Only the initial multi-MUM computation was considered for ProgressiveMauve and Parsnp2. Note: Parsnp2 took >48 h for chromosome 1 and 2, so these are omitted. Parsnp2 and ProgressiveMauve were run with 48 threads, while Mumemto was run single-threaded. C, D Time and memory scaling comparison for increasing sequence collection sizes of chr19. E, F Comparison of time and memory for a Mumemto-seeded Parsnp2 alignment pipeline compared to the original Parsnp2 pipeline, and G a comparison of the alignments from each pipeline. H Regions excluded from Minigraph-Cactus (MC) while aligning chr19 assemblies, compared to regions excluded by a Mumemto-seeded MC pipeline (overlaid on a MUM synteny plot in gray). I, J Syntenic view of MUMs vs tube map [15] view of the equivalent graph

Fig. 3

A, B MUM synteny visualization of collinear MUM blocks (red) and MUMs that break collinearity in a single sequence (gray (+)/green (−) based on orientation). C Large (>4 Mbp) syntenic region lost in HG02080.1, but recovered by partial MUMs (in gray). Evidence from non-collinear MUMs (D, E) and missing sequence present in partial MUMs (F) points a potential aberrant assembly artifact in the HG02080 paternal haplotype. G, H Genome-wide multi-MUMs reveal an interchromosomal join (confirmed to be a misassembly by HPRC [1]) in the aberrant regions

Fig. 4

A HPRC chr8 assemblies visualized with multi-MUM synteny. Regions of high multi-MEM density shown in red. (Zoom panels) Two examples of incorrectly oriented contigs during scaffolding, with contig breakpoints represented by diamond markers. Inversions shown in green. B Assemblies of chr3 across the potato family, shown with multi-MUM synteny and MEM density colored in red. (top) Density of gene and LTR retrotransposon annotations for potato accession A6-26 (shown in the top row of syntenic view)

Fig. 5

Aggregate length of partial MUMs that are not present in each genome assembly. A A. thaliana accessions are grouped by geographical region, and B potato (Solanum section Petota) are grouped by species

Algorithm 1

Find multi-MEMs/MUMs