Abstract—Basic Local Alignment Search Tool (BLAST) is one of the most widely used bioinformatics tools to determine similarities between genomic sequences. Ever since its inception several algorithmic improvements have been made to improve speed and runtime memory requirements without affecting the sensitivity and selectivity of the tool. Fast search algorithm (FSA) BLAST has been the most successful among such improvements with 20-30% faster processing rate. In this work a modified data structure is used for the hit detection process. Codes have been developed separately for use of existing and modified data structures and tested on sample database. It has been found that the use of new data structure results in up to 81% reduction in run time memory requirement and about 20% reduction in hit detection time without affecting sensitivity and selectivity of the algorithm.

Index Terms—BLAST, hit detection, neighborhood words, DFA, prefix word table, query pointers, space complexity, time complexity, blosum matrix.

M. Anuradha is with the Department Of Computer Science and Systems Engineering, Andhra University, Visakhapatnam – 530003, Andhrapradesh, India (phone: 91-044-22435134; mobile: 91-9444412833; anuradha_malempati@yahoo.com).
K. Suman Nelson is with Google India, Hyderabad, Andhrapradesh, India (e-mail: suman.nelson@gmail.com).
P. V. G. D. Prasad Reddy is with the Department Of Computer Science and Systems Engineering, Andhra university, Visakhapatnam - 530 003, Andhrapradesh, India (e-mail: prof.prasadreddy@gmail.com).

Cite: M. Anuradha , K. Suman Nelson, and P. V. G. D. Prasad Reddy, "Improved Hit Detection Algorithm for FSA Protein BLAST," International Journal of Bioscience, Biochemistry and Bioinformatics vol. 2, no. 2, pp. 71-75, 2012.