High speed BLASTN: an accelerated MegaBLAST search tool

Sequence alignment is a long standing problem in bioinformatics. The Basic Local Alignment Search Tool (BLAST) is one of the most popular and fun-damental alignment tools. The explosive growth of biological sequences calls for speedup of sequence alignment tools such as BLAST. To this end, we de-velop high speed BLASTN (HS-BLASTN), a parallel and fast nucleotide database search tool that ac-celerates MegaBLAST––the default module of NCBI-BLASTN. HS-BLASTN builds a new lookup table us-ing the FMD-index of the database and employs an accurate and effective seeding method to find short stretches of identities (called seeds) between the query and the database. HS-BLASTN produces the same alignment results as MegaBLAST and its com-putational speed is much faster than MegaBLAST. Specifically, our experiments conducted on a 12-core server show that HS-BLASTN can be 22 times faster than MegaBLAST and exhibits better parallel per-formance than MegaBLAST. HS-BLASTN is written in C++ and the related source code is available a