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, including nanopore sequencing reads.
• Existing methods face challenges with scalability and query speed, particularly for repetitive sequences.

Purpose of the Study:

• To develop an efficient pangenome indexing and querying tool for applications like nanopore sequencing read classification.
• To improve query speed and scalability compared to existing methods.

Main Methods:

• Development of Movi, a novel data structure based on the move structure and Burrows-Wheeler Transform (BWT).
• Implementation of optimized query algorithms minimizing cache misses and utilizing memory prefetching.
• Evaluation of Movi's performance for pangenome indexing and querying tasks.

Main Results:

• Movi demonstrates excellent scalability for repetitive text, with space complexity directly proportional to BWT runs (r).
• Movi achieves up to 30x faster query performance for classification tasks compared to existing methods.
• The constant-time query loop of Movi is suitable for real-time applications.

Conclusions:

• Movi provides a highly efficient and scalable solution for pangenome indexing and querying.
• Its speed and real-time suitability make it valuable for adaptive sampling in nanopore sequencing.