Movi 2: Fast and Space-Efficient Queries on Pangenomes

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Compressed indexing is vital for pangenomics to manage large datasets and minimize reference bias.
• The original Movi index offered speed and locality but suffered from a high memory footprint.

Purpose of the Study:

• To introduce Movi 2, a novel compressed index with substantially reduced size and memory requirements.
• To explore sampling strategies for balancing query speed and space efficiency in Movi 2.

Main Methods:

• Development of new methods to decrease the size and memory usage of move-structure indexes.
• Implementation of sampling approaches to allow for adjustable query and space efficiency.

Main Results:

• The most compressed Movi 2 version achieved over a fivefold reduction in space compared to the original Movi index.
• Movi 2 demonstrated superior performance in both time and memory footprint against existing methods, including r-index and the previous Movi.
• Effective application to large pangenome collections, such as the Human Pangenome Reference Consortium (HPRC) releases.

Conclusions:

• Movi 2 offers significant improvements in space efficiency for compressed indexes in pangenomics.
• The new methods provide flexible trade-offs between query performance and memory usage.
• Movi 2 represents a state-of-the-art solution for analyzing large pangenome datasets.