Important Algorithms
- Needleman and Wunsch (1970)
A global alignment that was
first developed without gap functionality: The method uses a dynamic procedure,
which is more efficient and faster in comparison with the calculation of all
possible alignments. This calculation is still too time-consuming for the
analysis of huge databases. It is very time intensive due to its dynamic procedure. A
dynamic procedure is a solution to a problem that is broken down into
subproblems, and the best results are then compared.
- Smith and Waterman (1981)
A local
alignment that was originally developed without gap functionality: The method
is very similar to that of Needleman and Wunsch and also quite time-consuming.
- FastA (Pearson and Lipman 1988)
A local
alignment that is very fast due to the use of a heuristic method (making
assessments to get almost exact results): The method identifies short word
regions and then uses a dynamic procedure to obtain a gapped alignment.
- BLAST (Altschul et al. 1990)
A local
alignment that can identify segment pairs of fixed length quickly due to the
use of a heuristic method. Segments are then prolonged until preset threshold
parameters are reached. BLAST is up to 100-fold faster than the Smith and
Waterman algorithm.
- Gapped BLAST (Altschul et al. 1997)
A local
alignment that looks only for a single segment pair: This segment pair is then
prolonged by gaps in both directions. The gapped BLAST algorithm is three times
faster than the ungapped BLAST algorithm.
