Movi: a fast and cache-efficient full-text pangenome index

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Pangenome indexes are crucial for analyzing large genomic datasets, particularly for rapid classification of sequencing reads.
• Existing compressed-index data structures like the FM index and r-index have limitations in space and query time for complex pangenomes.
• The move structure offers a novel approach with O(r) space and O(1)-time queries, where r is the number of runs in the Burrows-Wheeler Transform (BWT).

Conclusions:

• Movi provides a highly efficient solution for pangenome indexing and rapid read classification.
• The move structure, as implemented in Movi, offers significant performance advantages for large-scale genomic analyses.
• Movi is well-suited for real-time applications such as adaptive sampling in nanopore sequencing due to its speed and predictable query times.