BLAST Algorithm
Stephen F. Altschul · Encyclopedia of Life Sciences · 2014
Abstract BLAST is an acronym for ‘Basic Local Alignment Search Tool’. Members of the BLAST family of database search programs take as input a query deoxyribonucleic acid (DNA) or protein sequence, and search a DNA or protein sequence database 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. The BLAST algorithm first seeks near‐perfect matches to words within a query sequence, and then extends these matches to determine whether they are contained within longer, high‐scoring local alignments. BLAST approximates the rigorous Smith–Waterman local alignment algorithm; it permits a chance of missing weak sequence similarities in exchange for greatly increased speed. Key Concepts: Local sequence alignment is used for similarity searches of sequence databases. The Smith–Waterman algorithm is a rigorous dynamic programming method for finding optimal local alignments. BLAST is a fast, heuristic approximation to the Smith–Waterman algorithm. An analytic theory describes the optimal scores of ungapped local alignments. The statistical parameters for BLAST's gapped local alignments are precomputed by random simulation. Very efficient algorithms exist for finding perfect or near‐perfect word matches. BLAST finds weak local alignments if they contain near‐perfect word matches. BLAST provides a trade‐off between speed and the probability of missing statistically significant alignments. A variety of specialized BLAST programs are adapted to searching DNA or protein sequence databases with DNA or protein query sequences. PSI‐BLAST increases the sensitivity of protein database searches by constructing a protein profile from the results of a regular BLAST search.