1、Alignment methods,Introduction to global and local sequence alignment methods Global : Needleman-Wunch Local : Smith-Waterman Database Search BLAST FASTA,Why search sequence databases?,I have just sequenced something. What is known about the thing I sequenced? I have a unique sequence. Is there simi
2、larity to another gene that has a known function? I found a new protein in a lower organism. Is it similar to a protein from another species?,Perfect Searches,First “hit” should be an exact match. Next “hits” should contain all of the genes that are related to your gene (homologs) Next “hits” should
3、 be similar but are not homologs,How does one achieve the “perfect search”?,Comparison Matrices (PAM vs. BLOSUM) Database Search Algorithms Databases Search Parameters Expect Value-change threshold for score reporting Translation-of DNA sequence into protein Filtering-remove repeat sequences,Alignme
4、nt Algorithms,Global : Needleman-Wunch Local : Smith-Watermann These two dynamic programming alignment algorithm are guaranteed to give OPTIMAL alignments But O(m*n) quadraticSkip to Scoring Matrixes,Alignment Methods,Learning objectives-Understand the principles behind the Needleman-Wunsch method o
5、f alignment. Understand how software operates to optimally align two sequences,Needleman-Wunsch Method (1970),Output: An alignment of two sequences is represented by three lines The first line shows the first sequence The third line shows the second sequence. The second line has a row of symbols. Th
6、e symbol is a vertical bar wherever characters in the two sequences match, and a space where ever they do not. Dots may be inserted in either sequence to represent gaps.,Needleman-Wunsch Method (cont. 1),For example, the two hypothetical sequencesabcdefghajklmabbdhijkcould be aligned like this abcde
7、fghajklm| | | | abbd.hijk As shown, there are 6 matches, 2 mismatches, and one gap of length 3.,Needleman-Wunsch Method (cont. 2),The alignment is scored according to a payoff matrix $payoff = match = $match,mismatch = $mismatch,gap_open = $gap_open,gap_extend = $gap_extend ;For correct operation, m
8、atch must be positive, and the other entries must be negative.,Needleman-Wunsch Method (cont. 3),Example Given the payoff matrix $payoff = match = 4,mismatch = -3,gap_open = -2,gap_extend = -1 ;,Needleman-Wunsch Method (cont. 4),The sequences abcdefghajklmabbdhijk are aligned and scored like this a
9、b c d e f g h a j k l m| | | | | | a b b d . . . h i j kmatch 4 4 4 4 4 4 mismatch -3 -3gap_open -2gap_extend -1-1-1 for a total score of 24-6-2-3 = 13.,Needleman-Wunsch Method (cont. 5),The algorithm guarantees that no other alignment of these two sequences has a higher score under this payoff matr
10、ix.,Needleman-Wunsch Method (cont. 6) Dynamic Programming,Potential difficulty. How does one come up with the optimal alignment in the first place? We now introduce the concept of dynamic programming (DP).DP can be applied to a large search space that can be structured into a succession of stages su
11、ch that:1) the initial stage contains trivial solutions to sub-problems2) each partial solution in a later stage can be calculated by recurring on only a fixed number of partial solutions in an earlier stage.3) the final stage contains the overall solution.,Three steps in Dynamic Programming,1. Init
12、ialization2 Matrix fill or scoring3. Traceback and alignment,Two sequences will be aligned.GAATTCAGTTA (sequence #1) GGATCGA (sequence #2)A simple scoring scheme will be usedSi,j = 1 if the residue at position I of sequence #1 is the same as the residue at position j of the sequence #2 (called match
13、 score)Si,j = 0 for mismatch scorew = gap penalty,Initialization step: Create Matrix with M + 1 columns and N + 1 rows. First row and column filled with 0.,Matrix fill step: Each position Mi,j is defined to be the MAXIMUM score at position i,j Mi,j = MAXIMUM Mi-1, j-1 + si,j (match or mismatch in th
14、e diagonal)Mi, j-1 + w (gap in sequence #1)Mi-1, j + w (gap in sequence #2),Fill in rest of row 1 and column 1,Fill in column 2,Fill in column 3,Column 3 with answers,Fill in rest of matrix with answers,Traceback step: Position at current cell and look at direct predecessors,Traceback step: Position
15、 at current cell and look at direct predecessors,Seq#1 G A A T T C A G T T A| | | | | | Seq#2 G G A T - C - G - - A,Needleman-Wunsch Method Dynamic Programming,The problem with Needleman-Wunsch is the amount of processor memory resources it requires. Because of this it is not favored for practical u
16、se, despite the guarantee of an optimal alignment. The other difficulty is that the concept of global alignment is not used in pairwise sequence comparison searches.,Needleman-Wunsch Method Typical output file,Global: HBA_HUMAN vs HBB_HUMAN Score: 290.50HBA_HUMAN 1 VLSPADKTNVKAAWGKVGAHAGEYGAEALERMFL
17、SFPTTKTYFP 44|:| :|: | | | : | | | |: : :| |: :| HBB_HUMAN 1 VHLTPEEKSAVTALWGKVNVDEVGGEALGRLLVVYPWTQRFFE 43HBA_HUMAN 45 HF.DLS.HGSAQVKGHGKKVADALTNAVAHVDDMPNALSAL 83| | |: :| | | : :|:|: : | HBB_HUMAN 44 SFGDLSTPDAVMGNPKVKAHGKKVLGAFSDGLAHLDNLKGTFATL 88HBA_HUMAN 84 SDLHAHKLRVDPVNFKLLSHCLLVTLAAHLPAEFTP
18、AVHASLDKF 128|:| | | |:| : |: | | | | |: | HBB_HUMAN 89 SELHCDKLHVDPENFRLLGNVLVCVLAHHFGKEFTPPVQAAYQKV 133HBA_HUMAN 129 LASVSTVLTSKYR 141:| |: | | HBB_HUMAN 134 VAGVANALAHKYH 146%id = 45.32 %similarity = 63.31 Overall %id = 43.15; Overall %similarity = 60.27,Smith-Waterman Algorithm Advances in Appli
19、ed Mathematics, 2:482-489 (1981),The Smith-Waterman algorithm is a local alignment tool used to obtain sensitive pairwise similarity alignments. Smith-Waterman algorithm uses dynamic programming. Operating via a matrix, the algorithm uses backtracing and tests alternative paths to the highest scorin
20、g alignments, and selects the optimal path as the highest ranked alignment. The sensitivity of the Smith-Waterman algorithm makes it useful for finding local areas of similarity between sequences that are too dissimilar for alignment. The S-W algorithm uses a lot of computer memory. BLAST and FASTA
21、are other search algorithms that use some aspects of S-W.,Smith-Waterman (cont. 1),a. It searches for both full and partial sequence matches . b. Assigns a score to each pair of amino acids-uses similarity scores-uses positive scores for related residues-uses negative scores for substitutions and ga
22、ps c. Initializes edges of the matrix with zeros d. As the scores are summed in the matrix, any sum below 0 isrecorded as a zero. e. Begins backtracing at the maximum value foundanywhere in the matrix. f. Continues the backtrace until the score falls to 0.,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
23、 0 0 0 5 0 5 0 0 0 0 0 0 0 0 0 3 0 2012 4 0 0 0 10 2 0 0 0 12182214 6 0 2 16 8 0 0 4101828 20 0 0 82113 5 0 41020 27 0 0 6131812 4 0 416 26,H E A G A W G H E E,P A W H E A E,Smith-Waterman (cont. 2),Put zeros on borders. Assign initial scores based on a scoring matrix. Calculate new scores based on
24、adjacent cell scores. If sum is less than zero or equal to zero begin new scoring with next cell.,This example uses the BLOSUM45 Scoring Matrix with a gap extension penalty of -3,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 5 0 0 0 0 0 0 0 0 0 3 0 2012 4 0 0 0 10 2 0 0 0 12182214 6 0 2 16 8
25、 0 0 4101828 20 0 0 82113 5 0 41020 27 0 0 6131812 4 0 416 26,H E A G A W G H E E,P A W H E A E,Smith-Waterman (cont. 3),Begin backtrace at the maximum value found anywhere on the matrix. Continue the backtrace until score falls to zero,AWGHE | | AW-HE,Path Score=28,Calculation of percent similarity
26、,A W G H E A W - H E,Blosum45 SCORES,5 15 -5 10 6,GAP EXT. PENALTY,-3,% SIMILARITY = NUMBER OF POS. SCORES DIVIDED BY NUMBER OF AAs IN REGION x 100,% SIMILARITY = 4/5 x 100 = 80%,Scoring Matrix,BLOSUM and PAM BLOSUM62 PAM250 Higher number in BLOSUM Lower number is PAM Deals with MORE close homologue sequences So if you want to find more distantly related homologue, use BLOSUM 50 or lower instead of BLOSUM62,
