Volume 2 Number 2 (Mar. 2012)
Home > Archive > 2012 > Volume 2 Number 2 (Mar. 2012) >
IJBBB 2012 Vol.2(2): 71-75 ISSN: 2010-3638
DOI: 10.7763/IJBBB.2012.V2.74

Improved Hit Detection Algorithm for FSA Protein BLAST

M. Anuradha , K. Suman Nelson, and P. V. G. D. Prasad Reddy

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.

General Information

ISSN: 2010-3638
Frequency: Bimonthly (2011-2015); Quarterly (Since 2016)
DOI: 10.17706/IJBBB
Editor-in-Chief: Prof. Ebtisam Heikal 
Abstracting/ Indexing: Electronic Journals Library, Chemical Abstracts Services (CAS), Engineering & Technology Digital Library, Google Scholar, and ProQuest.
E-mail: ijbbb@iap.org
  • Jan 05, 2017 News!

    [CFP] 2017 the annual meeting of IJBBB Editorial Board, ICOCB 2017, will be held in Jakarta, Indonesia during May 24-26, 2017. [Click]

  • Sep 12, 2017 News!

    The papers published in Vol. 7, No. 4 have all received dois from Crossref. [Click]

  • Aug 29, 2017 News!

    IJBBB Vol. 7, No. 4 has been published online!  [Click]

  • Jun 12, 2017 News!

    The papers published in Vol. 7, No. 3 have all received dois from Crossref. [Click]

  • May 19, 2017 News!

    IJBBB Vol. 7, No. 3 has been published online!  [Click]

  • Read more>>