Dynamic programming guarantees to find the best solution but has a complexity of O(mn). Heuristic algorithms do not guarantee the best solution but are very fast in comparison with deterministic algorithms such as dynamic programming.
BLAST finds high scoring local alignments between a query sequence and a target database, both of which can be either DNA or protein. The idea is that true match alignments are very likely to contain short stretches of high scoring identities. We use these as seed and expand the alignments. BLAST makes a list of all neighborhood words of a fixed length that would match the query sequence somewhere with score higher than some threshold.
FASTA uses a multistep approach to finding local high scoring alignments:
1. Lookup table to locate all identically matching words of length ktup between 2 sequences.
2. Lookup diagonals with many mutually supporting word matches
3. Pursue the best diagonal, extending the exact word matches to find maximal scoring ungapped regions. This is analogous to hit extension in blast.
4. Check to see if any of these ungapped regions can be joined by a gapped region, allowing for gap costs.
5. The highest scoring candidate matches in a search database are realigned using the full dynamic programming algorithm, but restricted to a subregion of the dynamic programming matrix forming a band around the candidate heuristic search.