Mem-based pangenome indexing for k-mer queries

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Pangenomes are expanding due to advanced long-read sequencing technologies.
• Existing pangenome analysis methods face limitations in computational cost, variation handling, and query flexibility.
• K-mer and de Bruijn graph-based indexes are restricted to fixed substring lengths.

Purpose of the Study:

• To develop a new pangenome indexing method, Maximal Exact Match Ordered (MEMO), that overcomes the limitations of current approaches.
• To enable arbitrary-length queries and efficient conservation analysis within pangenomes.
• To provide a flexible and scalable tool for studying sequence composition and conservation.

Main Methods:

• Developed MEMO, a pangenome index based on maximal exact matches (MEMs).
• Implemented arbitrary-length query capabilities for membership and conservation queries.
• Evaluated MEMO's index size and query performance against existing methods like KMC3 and PanKmer.

Main Results:

• MEMO achieves significantly smaller index sizes compared to KMC3 and PanKmer for large pangenomes (e.g., 8.8x smaller than KMC3).
• MEMO supports both k-mer presence/absence and conservation queries across pangenomic windows.
• Conservation queries using MEMO are faster than existing methods, demonstrated by a 2.5x speedup in the human leukocyte antigen locus analysis.

Conclusions:

• MEMO offers a flexible and efficient solution for pangenome analysis, overcoming limitations of k-mer-based methods.
• Its small index size, arbitrary-length query support, and speed make it suitable for studying substring conservation in large pangenomes.
• MEMO is a valuable tool for visualizing and analyzing sequence variation and conservation across diverse genomes.