RosaSeed: Faster and Accurate Short Read Alignment Using a Configurable Seeding Strategy

Traditional methods of aligning short DNA reads, like the commonly used BWA-MEM2, require a significant portion of their time to create "seeds". RosaSeed, a new short read alignment algorithm, uses a flexible seeding system that speeds up alignment without sacrificing the accuracy seen in BWA-MEM2. This system replaces BWA-MEM2's seeding process, providing candidate seeds that the BWA-MEM2's chain and extend alignment pipeline can use. The end result is standard SAM output, which is ready for further variant analysis.

RosaSeed was tested on both computer-generated and real-world short read data. The study compared RosaSeed's seeding speed, time to convert FASTQ to SAM, alignment accuracy, and memory use to BWA-MEM2, Minimap2, Bowtie2, and Enumerated Radix Tree (ERT) algorithms. For single-threaded execution, RosaSeed using the suggested configuration was 13.06 times faster at generating seeds and 3.85 times faster at converting FASTQ to SAM compared to BWA-MEM2.

RosaSeed also outperformed ERT, ERT2, Minimap2, and Bowtie2 in seed processing and fastq-to-SAM time. It needed only 49.61 GB of memory at its peak, 25% less than ERT and ERT2 while still maintaining alignment accuracy similar to BWA-MEM2.

The researchers also compared RosaSeed to minibwa, a prefetch-optimized FM index aligner, on a powerful workstation. The optimized version of RosaSeed, named miniRosaSeed, was 2.12 times faster at converting FASTQ to SAM than minibwa, achieving a 2.58% higher standard accuracy. Compared to Strobealign, miniRosaSeed was 2.18 times faster with a 3.1% increase in standard accuracy.

For multi-threaded execution, miniRosaSeed was both faster and more accurate than minibwa up to 26 software threads on the workstation. RosaSeed offers various memory and performance configurations, letting users choose settings that fit their specific computing environment while keeping alignment quality similar to BWA-MEM2.