Heuristic Vs. Rigorous
- Both FastA and BLAST are approximations of Smith-Waterman algorithm. Hence, both perform heuristic filtering of the database.
- Distantly related sequences (e.g. - containing many substitutions and gaps) are less likely to be discovered with heuristic applications
- Smith-Waterman finds similarities in a rigorous way (e.g. - calculates the accumulating score for every cell in the matrix). Hence, it runs 100-1000 slower than FastA and BLAST.
- Hardware accelerators (e.g Bioccelerator, BioXL/P) make rigorous algorithms practical.