Sapling

Sapling accelerates suffix array queries by augmenting the suffix array with a learned piecewise linear model to speed sequence alignment in large-scale genomic datasets.

Key Features:

• Suffix array augmentation: Augments the suffix array with a learned data model to reduce the number of binary-search steps required for queries.
• Piecewise linear model: Employs a piecewise linear model to predict suffix array positions and enable more rapid queries than traditional binary search.
• Learned models and neural networks: Investigates various neural network models and selects a compact, practical learned model for augmentation.
• Cache-miss reduction: Reduces cache misses caused by extensive memory accesses inherent to binary-search traversal of suffix arrays.
• Performance improvement: Demonstrates more than double the query speed of conventional methods in benchmark comparisons.
• Low memory overhead: Adds less than 1% to the suffix array's memory footprint.
• Benchmarking against aligners: Outperforms optimized binary search techniques and several existing read aligners across tested datasets.

Scientific Applications:

• Sequence alignment acceleration: Speeds up sequence alignment workflows by reducing suffix array query time.
• Read alignment throughput: Increases throughput for read alignment tasks through faster index queries.
• Genomic indexing and pattern matching: Improves performance of indexing and exact pattern matching in genomic sequences.
• Large-scale genomics: Enables faster analysis of genomic datasets from humans, bacteria, and plants.

Methodology:

Integrates a learned data model with the suffix array and employs a piecewise linear model; investigates neural network models to identify a compact practical approach; benchmarks against optimized binary search and existing read aligners on human, bacterial, and plant genomic datasets.