PPT Slide
For searching whole databases and genomes dynamics programming is too slow. Database size = 108 (100 million residues) and the query might be 103 (1000 amino=acids). So 1011 comparisons. Even at 107 per second that takes 1000s = 17 minutes.
‘Heuristic’ approximations have been developed that usually give almost the same results. These methods do not guarantee optimal alignments.
- BLAST
Altschul et al (1990) Ungapped
Altschul & Gish (1996) Gapped
The algorithm looks for identities that seeds further alignment based on similarities.