DYNAMIC PROGRAMMING Vs HUERISTIC METHODS

Dynamic Programming Methods

In dynamic programming every pair of residues are compared and an alignment is generated to give a maximum score.

Dynamic programming method used to create a global alignment is Needleman – Wunch Algorithm.

Dynamic programming method used for creating a local alignment is the Smith-Waterman Algorithm.

Heuristic Methods

Dynamic Programming methods are guaranteed to find the optimal alignment. In particular the scoring scheme involving Affine gap score is generally regarded as providing the most sensitive sequence matches. However, they are not fastest sequence alignment procedures. For applications like homology searches using large database, speed becomes a prime issue. The dynamic programming has time complexity of the order of O (n*m) where n and m are the lengths of the sequences considered for comparisons (i.e., n and m are number of residues/nucleotides) to make a search in a database containing 100 million residues we need to evaluate about 10 to the power 11 matrix elements.

This may take several hours of computer time. If we want to make homology searches for many sequences it becomes very tiring job as far as computer time is concerned.

In order to reduce the time consumed for comparison a few heuristic methods have been developed. The word heuristic means an alternative procedure mostly based on probably an educated guess. In heuristic methods there is always trade-off between sensitivity and speed. The most popular methods are BLAST and FASTA.