BLAST Algorithm

Stephen F Altschul, National Center for Biotechnology Information, Bethesda, Maryland, USA

Published online: September 2005

DOI: 10.1038/npg.els.0005253

BLAST is an acronym for basic local alignment search tool; the BLAST family of database search programs takes as input a query DNA or protein sequence, and search DNA or protein sequence databases for similarities that may indicate homology. The programs implement variations of the BLAST algorithm, which is a heuristic method for rapidly finding local alignments with scores sufficiently high to be statistically significant.

Keywords: local alignment; homology search; sequence similarity; statistical significance; PSI-BLAST

 References
    Altschul SF and Gish W (1996) Local alignment statistics. Methods in Enzymology 266: 460–480.
    Altschul SF, Gish W, Miller W, Myers EW and Lipman DJ (1990) Basic local alignment search tool. Journal of Molecular Biology 215: 403–410.
    Altschul SF, Madden TL, Schäffer AA, et al. (1997) Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research 25: 3389–3402.
    Gish W and States DJ (1993) Identification of protein coding regions by database similarity search. Nature Genetics 3: 266–272.
    Henikoff S and Henikoff JG (1992) Amino acid substitution matrices from protein blocks. Proceedings of the National Academy of Sciences of the United States of America 89: 10915–10919.
    Karlin S and Altschul SF (1990) Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. Proceedings of the National Academy of Sciences of the United States of America 87: 2264–2268.
    Schäffer AA, Wolf YI, Ponting CP, et al. (1999) IMPALA: matching a protein sequence against a collection of PSI-BLAST-constructed position-specific score matrices. Bioinformatics 15: 1000–1011.
    Wheeler DL, Church DM, Lash AE, et al. (2001) Database resources of the National Center for Biotechnology Information. Nucleic Acids Research 29: 11–16.
    Zhang Z, Schäffer AA, Miller W, et al. (1998) Protein sequence similarity searches using patterns as seeds. Nucleic Acids Research 26: 3986–3990.
    Zhang Z, Schwartz S, Wagner L and Miller W (2000) A greedy algorithm for aligning DNA sequences. Journal of Computational Biology 7: 203–214.
 Further Reading
    Altschul SF and Koonin EV (1998) Iterated profile searches with PSI-BLAST: a tool for discovery in protein databases. Trends in Biochemical Sciences 23: 444–447.
    Altschul SF, Boguski MS, Gish W and Wootton JC (1994) Issues in searching molecular sequence databases. Nature Genetics 6: 119–129.
    Altschul SF, Bundschuh R, Olsen R and Hwa T (2001) The estimation of statistical parameters for local alignment score distributions. Nucleic Acids Research 29: 351–361.
    book Baxevanis AD and Ouellette BFF (2001) Bioinformatics: A Practical Guide to the Analysis of Genes and Proteins, 2nd edn. New York: John-Wiley.
    Dembo A, Karlin S and Zeitouni O (1994) Limit distribution of maximal non-aligned two-sequence segmental score. Annals of Probability 22: 2022–2039.
    book Ewens WJ and Grant GR (2001) Statistical Methods in Bioinformatics. New York: Springer-Verlag.
    Schäffer AA, Aravind L, Madden TL, et al. (2001) Improving the accuracy of PSI-BLAST protein database searches with composition-based statistics and other refinements. Nucleic Acids Research 29: 2994–3005.
    Smith TF and Waterman MS (1981) Identification of common molecular subsequences. Journal of Molecular Biology 147: 195–197.
    Smith TF, Waterman MS and Burks C (1985) The statistical distribution of nucleic acid similarities. Nucleic Acids Research 13: 645–656.
    Wilson AC, Carlson SS and White TJ (1977) Biochemical evolution. Annual Review of Biochemistry 46: 573–639.
 Web Links
    ePath National Center for Biotechnology Information BLAST server http://www.ncbi.nlm.nih.gov/BLAST/
    ePath Washington University BLAST server http://blast.wustl.edu/

Related Sub-Topics:

Protein Structure | Bioinformatics | Techniques and Tools in Molecular Biology | Computational Molecular Biology
Contact Editor close
Submit a note to the editor about this article by filling in the form below.

* Required Field

Article Title: BLAST Algorithm
 
How to Cite close
Altschul, Stephen F(Sep 2005) BLAST Algorithm. In: eLS. John Wiley & Sons Ltd, Chichester. http://www.els.net [doi: 10.1038/npg.els.0005253]