An incrementally updatable and scalable system for large-scale sequence search using the Bentley-Saxe transformation

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Existing indexing schemes for raw sequencing data are often approximate to save space.
• Recent exact indexes (Mantis, VariMerge, Bifrost) offer potential for complex analyses but lack scalability and efficient data insertion.
• Large, growing repositories of sequencing data require indexes that can handle thousands of experiments and accommodate new data efficiently.

Purpose of the Study:

• To develop a scalable and updatable exact index for searching large raw sequencing datasets.
• To extend the Mantis index to support efficient updates, creating Dynamic Mantis.
• To evaluate the performance of Dynamic Mantis against existing exact indexes in terms of scalability, construction time, query speed, and index size.

Main Methods:

• Extended the Mantis index using the Bentley-Saxe transformation to enable efficient updates.
• Constructed a Dynamic Mantis index with approximately 40,000 samples from the Sequence Read Archive (SRA) by incrementally adding samples.
• Benchmarked Dynamic Mantis against VariMerge and Bifrost using metrics including index construction time, memory usage, query performance, and index size.

Main Results:

• Dynamic Mantis demonstrated scalability by successfully indexing over 39,000 samples, significantly outperforming VariMerge (5K samples) and Bifrost (80 samples).
• Dynamic Mantis exhibited superior efficiency, with faster index construction and query times compared to Bifrost.
• Dynamic Mantis produced smaller index sizes, approximately 2.5x smaller than Bifrost and half the size of VariMerge.

Conclusions:

• Dynamic Mantis provides a scalable and updatable solution for exact searching of large raw sequencing data.
• The developed index offers significant improvements in efficiency and size compared to existing state-of-the-art methods.
• Dynamic Mantis is a promising tool for managing and analyzing the ever-increasing volume of genomic sequencing data.