title: High speed BLASTN: an accelerated MegaBLAST search tool.
abstract: Sequence alignment is a long standing problem in bioinformatics. The Basic Local Alignment Search Tool (BLAST) is one of the most popular and fundamental alignment tools. The explosive growth of biological sequences calls for speedup of sequence alignment tools such as BLAST. To this end, we develop high speed BLASTN (HS-BLASTN), a parallel and fast nucleotide database search tool that accelerates MegaBLAST--the default module of NCBI-BLASTN. HS-BLASTN builds a new lookup table using 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 computational 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 performance than MegaBLAST. HS-BLASTN is written in C++ and the related source code is available at https://github.com/chenying2016/queries under the GPLv3 license.
authors.affiliation: Guangdong Province Key Laboratory of Computational Science, School of Mathematics and Computational Science, Sun Yat-sen University, Guangzhou 510275, P. R. China.
authors.forename: Ying
authors.initials: Y
authors.lastname: Chen
authors.affiliation: Guangdong Province Key Laboratory of Computational Science, School of Mathematics and Computational Science, Sun Yat-sen University, Guangzhou 510275, P. R. China.
authors.forename: Weicai
authors.initials: W
authors.lastname: Ye
authors.affiliation: Guangdong Province Key Laboratory of Computational Science, School of Mathematics and Computational Science, Sun Yat-sen University, Guangzhou 510275, P. R. China lnszyd@mail.sysu.edu.cn.
authors.forename: Yongdong
authors.initials: Y
authors.lastname: Zhang
authors.affiliation: Guangdong Province Key Laboratory of Computational Science, School of Mathematics and Computational Science, Sun Yat-sen University, Guangzhou 510275, P. R. China Department of Mathematics, Syracuse University, Syracuse, NY 13244, USA yxu06@syr.edu.
authors.forename: Yuesheng
authors.initials: Y
authors.lastname: Xu
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D030561:Databases, Nucleic Acid; D015894:Genome, Human; D006801:Humans; D016415:Sequence Alignment / Q000379:methods*; D012984:Software