MEM-based pangenome indexing for k-mer queries

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Pangenomes are expanding due to high-quality long-read assemblies.
• Current pangenome analysis methods have limitations in studying sequence composition and conservation.
• Graph-based methods are computationally intensive, and k-mer methods are restricted to fixed substring lengths.

Purpose of the Study:

• To present Maximal Exact Match Ordered (MEMO), a new pangenome indexing method.
• To enable arbitrary-length queries and efficient conservation analysis within pangenomes.
• To overcome the limitations of existing pangenome indexing techniques.

Main Methods:

• Developed MEMO, a pangenome indexing method based on maximal exact matches (MEMs).
• Implemented MEMO to support both k-mer presence/absence (membership) and conservation queries.
• Indexed a pangenome of 89 human autosomal haplotypes.

Main Results:

• MEMO index size is significantly smaller (8.8x smaller than KMC3, 11.4x smaller than PanKmer).
• Achieved a 0.67 GB index size with decile resolution for the HPRC dataset.
• MEMO performed conservation queries 2.5x faster than other methods, e.g., 13.89 seconds for 31-mers in the HLA locus.

Conclusions:

• MEMO offers a flexible and efficient tool for pangenome analysis.
• Its small index size, arbitrary-length query capability, and speed address limitations of current methods.
• MEMO facilitates the study and visualization of substring conservation in large pangenomes.