Scrooge: a fast and memory-frugal genomic sequence aligner for CPUs, GPUs, and ASICs.

Area of Science:

• Bioinformatics and Computational Biology
• Genomic Sequence Analysis
• Algorithm Optimization

Background:

• Pairwise sequence alignment is a critical yet computationally intensive step in bioinformatics.
• Existing algorithms like GenASM show promise but suffer from inefficiencies in data movement and memory footprint.
• Accelerating sequence alignment is crucial for advancing large-scale genomic studies.

Purpose of the Study:

• To address inefficiencies in the GenASM algorithm for pairwise sequence alignment.
• To develop a faster and more memory-frugal genomic sequence aligner named Scrooge.
• To provide open-source implementations of Scrooge for both CPUs and GPUs.

Main Methods:

• Introduced three novel algorithmic improvements to reduce data movement, memory usage, and computational operations within the GenASM framework.
• Developed efficient CPU and GPU implementations of the Scrooge algorithm.
• Conducted systematic analyses of throughput and accuracy across various configurations and compared performance against existing aligners.

Main Results:

• Scrooge achieves significant speedups: 20.1x on CPU over KSW2 and 2.1x over GenASM for long reads.
• The GPU version of Scrooge demonstrates up to 80.4x speedup over KSW2 and 6.8x over GenASM.
• Estimated ASIC implementation of Scrooge shows 3.6x less chip area and 2.1x less power consumption than GenASM.

Conclusions:

• Scrooge offers substantial performance improvements in speed and memory efficiency for genomic sequence alignment.
• The algorithmic enhancements in Scrooge provide considerable benefits across different hardware platforms (CPU, GPU, ASIC).
• The findings guide future implementations and optimizations for efficient genomic data analysis.