DYNAMIC PROGRAMMING
The technique of dynamic programming can be applied to produce Global alignments via Needleman-Wunsch algorithm and local alignments via the Smith-Waterman algorithm.
LOCAL ALIGNMENT AND GLOBAL ALIGNMENT
There are two general models to view alignments. The first model considers similarity across the full extent of the sequences (Global alignment). The second focuses on the regions of similarity in parts ofthe sequence only.(it is local alignment). A search for local similarity may produce more biologically meaningful and sensitive results than a global alignment.
Global alignment: Needleman Wunsch algorithms.
Global alignments attempt to align every residue in every sequence and they are most useful when the sequences in the query set are similar and of roughly equal size. Needleman and Wunsch algorithm is used for computing a global alignment between two sequences and it is based on dynamic programming. The algorithm proposed a maximum match path way that can be obtained computationally by applying some rules. Here cells representing identities are scored 1 and cells representing mismatches are scored 0. This process examines each cell in the matrix and finally summation of cells is started. When this process is completed, the maximum match path way is constructed.
Thus in global alignment comparison of the two sequences over the entire length is done. The Needleman Wunsch algorithm for global alignment is time consuming to run if the sequences are long. This is a general algorithm for sequence comparison. It maximise a similarity score to give maximum score. Maximum match is the largest number of residues of one sequence that can be matched with another allowing for all possible deletions.
Local Alignment: - Smith-Waterman algorithm
Local alignments are more useful for dissimilar sequences that are suspected to contain regions of similarity or similar sequence motifs. Local alignment searches for regions of local similarity and need not include the entire length of the sequences. Local alignment methods are very useful for scanning databases. Smith Waterman algorithm is used for local alignments. Even if the two given sequences are dissimilar, there will be some local similarity between sequences. Smith Waterman algorithm is used to find out this local similarity.
The key feature of Smith-Waterman algorithm is that each cell in the matrix defines the end point of a potential arrangement. The algorithm thus begins by filling the edge elements with 0.0 (floating point) values. Now the remaining cells in the matrix are compared. Three functions are compared at a time and the maximum of these three is chosen. Once the matrix is complete, the highest score is located. It represents the end points of an alignment (with maximum local similarity).
In addition to these many score matrices have been devised that weight match between non-identical residues.
DAYHOFF MUTATION DATA MATRIX
The MD (mutation data) score is based on the concept of point accepted mutation (PAM). 1 PAM indicates the probability of a residue mutating during a distance in which a point mutation was accepted per 100 residues. In a mutation data matrix, the amino acids are arranged by assuming that positive values represent evolutionarily conservative replacements. Within the matrix, values greater than zero indicate likely mutations, values equal to 0 are neutral (random) and values less than zero indicate unlikely mutations.
BLOSUM MATRICES:
The most common task of sequence analysis is the detection of more distant relationships. BLOSUM matrices are derived in order to represent distant relationships more clearly. Here for each cluster, the sequence segments are arranged on the basis of minimum percentage identity. For each cluster the average contribution at each residue position is calculated. By setting different clustering percentages, different matrices can be produced.
Fast A and BLAST
The fast A and BLAST programs are local similarity search methods that concentrate on finding short identical matches between sequences BLAST (Basic Local Alignment Search Tool) all segment pairs which are identical. It is also a computational programming algorithm tool to calculate local alignments. Fast A and BLAST search methods have comparatively low speed. Hence Gapped BLAST method can be used to improve search speed.