Scrooge

Scrooge accelerates pairwise genomic sequence alignment by incorporating three algorithmic enhancements to GenASM that reduce data movement, memory footprint, and computational operations.

Key Features:

• Algorithmic Improvements: Scrooge introduces three algorithmic modifications to GenASM that minimize data movement, reduce memory footprint, and eliminate unnecessary computations.
• Efficient Implementations: Implementations for CPU and GPU platforms provide optimized execution on heterogeneous hardware.
• Performance Gains: On CPUs, Scrooge achieves 20.1×, 1.7×, and 2.1× speedups over KSW2, Edlib, and the CPU version of GenASM respectively; on GPUs, it attains 4.0×, 80.4×, 6.8×, 12.6×, and 5.9× speedups compared to the CPU version of Scrooge, KSW2, Edlib, Darwin-GPU, and the GPU implementation of GenASM respectively.
• Resource Efficiency: ASIC estimates indicate Scrooge uses 3.6× less chip area and consumes 21% less power than a GenASM-based ASIC while maintaining equivalent throughput.
• Throughput and Accuracy Analysis: Systematic analyses of throughput and accuracy across configurations inform optimal settings for different computing platforms.

Scientific Applications:

• Large-scale sequencing: High-throughput alignment suitable for large-scale sequencing projects involving long reads.
• Comparative genomics: Enables rapid pairwise alignments for comparative genomics analyses.
• High-throughput long-read processing: Supports processing of long reads with high throughput for applications requiring precise and fast alignments.

Methodology:

Three algorithmic modifications to GenASM to reduce data movement, memory footprint, and computations; CPU and GPU implementations; benchmarking against KSW2, Edlib, GenASM, and Darwin-GPU; and ASIC area and power estimation.