Sapling: accelerating suffix array queries with learned data models.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Genomic data expansion necessitates efficient sequence alignment algorithms.
• Suffix arrays accelerate alignment but suffer from cache misses due to binary search on large datasets.

Purpose of the Study:

• To develop and evaluate Sapling, a novel algorithm for faster sequence alignment.
• To improve the efficiency of suffix array queries using learned data models.

Main Methods:

• Developed Sapling, an algorithm integrating learned data models with suffix arrays.
• Investigated various neural network models and implemented a compact, piecewise linear model.
• Evaluated Sapling against optimized binary search and existing read aligners.

Main Results:

• Sapling achieved more than twofold speedup in sequence alignment across diverse genomes (human, bacteria, plants).
• The memory footprint increase was less than 1% of the suffix array size.
• Outperformed optimized binary search and widely used read aligners.

Conclusions:

• Sapling offers a significant improvement in sequence alignment speed and efficiency.
• The learned data model approach effectively reduces cache misses and accelerates queries.
• Sapling provides a practical and efficient solution for large-scale genomic data analysis.