Flexible seed size enables ultra-fast and accurate read alignment

Abstract

Read alignment to genomes is a fundamental computational step used in many bioinformatic analyses, and often, it is the computational bottleneck. Therefore, it is desirable to perform the alignment step as fast as possible without compromising accuracy. Most alignment algorithms consider a seed-and-extend approach, where the time-consuming seeding step identifies and decides on candidate mapping locations. Recently, several advances have been made on seeding methods for fast sequence comparison. We combine two such methods, syncmers and strobemers, in a novel seeding approach for constructing dynamic-sized fuzzy seeds and implement the method in a short-read aligner, strobealign. Firstly, we show that our seeding is fast to construct and effectively reduces repetitiveness in the seeding step using a novel metric E-hits. Secondly, we benchmark strobealign to traditional and recently proposed aligners on simulated and biological data and show that strobealign is several times faster than traditional aligners such as BWA and Bowtie2 at similar and sometimes higher accuracy while being both faster and more accurate than more recently proposed aligners. Our aligner can free up substantial time and computing resources needed for read alignment in many pipelines. Availabilityhttps://github.com/ksahlin/strobealign.