The week's pick
Random Articles
Reseach Article
BLOSUM Trie for Faster Hit Detection in FSA Protein BLAST
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 64 - Number 1 |
| Year of Publication: 2013 |
| Authors: M Anuradha, K Suman Nelson, P V G D Prasad Reddy |
10.5120/10602-5306
|
M Anuradha, K Suman Nelson, P V G D Prasad Reddy . BLOSUM Trie for Faster Hit Detection in FSA Protein BLAST. International Journal of Computer Applications. 64, 1 ( February 2013), 46-53. DOI=10.5120/10602-5306
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. A DFA with hashed prefix word structures for the hit detection process in FSA BLAST has been proposed in the earlier work. Coding of the algorithms and testing on protein samples showed that the use of the new structure resulted in significant reduction in run time space but not the hit detection time. This paper proposes the use of a BLOSUM trie structure which eliminates the process of computing neighborhood words, resulted in a reduction of up to 75% in hit detection time. Tests were conducted with different BLOSUM matrices and threshold values and the proposed algorithm was found to be beneficial in terms of space, time complexity and accuracy without compromising on sensitivity and selectivity of the currently being used algorithm.
References
- Pertsemlidis, A. and John, W. Fondon III. 2001. Tutorial - Having BLAST with bioinformatics (and avoiding BLASTphemy), Genome Biology 2(10).
- Altschul, S. F. Gish, W. Miller, W. Myers, E. W. and D. J. Lipman, D. J. 1990. Basic local alignment search tool. Journal of Molecular Biology, 215(3):403– 410.
- Altschul, S. F. Madden, T. L. Schaffer, A. A. Zhang, J. Zhang, Miller, Z. W. and D. J. Lipman, D. J. 1997. Gapped BLAST and PSI–BLAST: A new generation of protein database search programs. Nucleic Acids Research, 25(17):3389–3402.
- WU-BLAST [http://blast. wustl. edu/]
- Boysen, C. and Marc, A. Rieffel. 2004. Enhancing BLAST Performance by using paracel filtering package, Paracel Technology.
- Cameron, M. . Williams, H. E. and Cannane, A. 2004. Improved gapped alignment in BLAST. IEEE Transactions on Computational Biology and Bioinformatics, 1(3):116-129.
- Cameron, M. . Williams, H. E. and Cannane, A. 2006. A deterministic finite automaton for faster protein hit detection in BLAST, Journal of Computational Biology 13(4), 965–978.
- McGinnis, S. and T. L. Madden, T. L. 2004. BLAST: at the core of a powerful and diverse set of sequence analysis tools. Nucleic Acids Research, 32:W20–W25.
- Chen, X. L. 2004. personal communication.
- Shapaer, E. G. Robinson, M. Yee, D. Candlin, J. D. Mines, R. and Hunkapiller, T. 1996. Sensitivity and selectivity in protein similarity searches: A Comparison of Smith-Waterman in Hardware to BLAST and FASTA. Genomics,38, 179-191.
- Gotoh, O. 1982. An improved algorithm for matching biological sequences. Journal of Molecular Biology, 162(3):705–708.
- Jian, Y. McGinnis, S. and Madden, T. L. 2006. BLAST: improvements for better sequence analysis, W6–W9 Nucleic Acids Research, Vol. 34, Web Server issue doi:10. 1093/nar/gkl164
- Noé,* L. and Kucherov, G. 2004. Improved hit criteria for DNA local alignment, BMC Bioinformatics, 5:149 doi:10. 1186/1471-2105-5-149.
- Delaney, S. Butler, G. Lam, C. and Thiel, L. Three Improvements to the BLASTP Search of Genome Databases, 0-7695-0686-0/00 $10. 00 _ 2000 IEEE
- Cameron, M. and Williams, H. E. 2007. Comparing Compressed Sequences for Faster Nucleotide BLAST Searches, IEEE Transactions.
- Afratis, P. Galanakis, C. Sotiriades, E. Mplemenos, G. G. Chrysos, G. Papaefstathiou, I. and Pnevmatikatos, D. Design and Implementation of a Database Filter for BLAST Acceleration, 978-3-9810801-5-5/DATE09 © 2009 EDAA.
- Guo, X. Wang, H. Vijay, D. Design of a FPGA-Based Parallel Architecture for BLAST Algorithm with Multi-hits Detection, 2011 Eighth International Conference on Information Technology: New Generations, 978-0-7695-4367-3/11 $26. 00 © 2011 IEEE, DOI 10. 1109/ITNG. 2011. 122.
- Boratyn, G. M. Schaffer, A. A. Agarwala, R. Altschul, S. F. Lipman, D. J. and Madden, T. L. 2012. Domain enhanced lookup time accelerated BLAST, Biol Direct Apr 17;7(1):12.
- Anuradha, M. Suman Nelson, K. and Prasad Reddy, P. V. G. D. March 2012. Improved hit detection algorithm for FSA protein BLAST. International Journal of Bioscience, Biochemistry and Bioinformatics, Vol. 2, No. 2:61-65.
- Wilbur, W. J. and Lipman, D. J. 1983. Rapid similarity searches of nucleic acid and protein data banks. Proceedings of the National Academy of Sciences USA, 80(3):726–730.
- Karlin, S. and Altschul, S. F. 1990. Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. Proceedings of the National Academy of Sciences USA, 87(6):2264–2268.
- Altschul, S. F. Boguski, M. Gish, W. and Wootton, J. 1994. Issues in searching molecular sequence databases. Nature Genetics, 6:119–129.
- Altschul, S. F. and Gish, W. Local alignment statistics. Methods in Enzymology, 266:460–480, 1996.
- Altschul, S. F. Bundschuh, R. Olsen, R. . and Hwa, T. 2001. The estimation of statistical parameters for local alignment score distributions. Nucleic Acids Research, 29(2):351–361.
- Henikoff, S. and Henikoff, J. 1992. Amino acid substitution matrices from protein blocks. Proceedings of the National Academy of Sciences USA, 89(22):10915–10919.
Index Terms
Keywords