& BLS 9/7/7 Define: - Define Score of Optimal lignment using Recursion S(i, j) = Score of optimal alignment of x..i and y..j Initial conditions: x..i

Size: px

Start display at page:

Download "& BLS 9/7/7 Define: - Define Score of Optimal lignment using Recursion S(i, j) = Score of optimal alignment of x..i and y..j Initial conditions: x..i"

越额尔德特
6 years ago
Views:

1 & BLS 9/7/7 BB 444/544 Lecture 8 Finish: Dynamic Programming Global vs Local lignment Scoring Matrices & lignment Statistics BLS #8_Sept7 Required Reading (before lecture) Last week: - for Lectures 4-7 Pairwise Sequence lignment, Dynamic Programming, Global vs Local lignment, Scoring Matrices, Statistics Xiong: hp 3 Eddy: What is Dynamic Programming? 4 Nature Biotechnol :99 Wed Sept 5 - for Lecture 7 & Lab 3 Database Similarity Searching: BLS (nope, more DP) hp 4 - pp 5-6 Fri Sept - for Lecture 8 (will finish on Monday) BLS variations; BLS vs FS hp 4 - pp 5-6 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 ssignments & nnouncements hp 3- Sequence lignment ues Sept 4 - Lab # Exercise Writeup due by 5 PM Send via to Pete Zaback petez@iastate.edu (For now, no late penalty - just send SP) Wed Sept 5 - Notes for Lecture 5 posted online - HW# posted online & sent via & handed out in class Fri Sept 4 - HW# Due by 5 PM Fri Sept - Exam # BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 3 SEION II SEQUENE LIGNMEN Xiong: hp 3 Pairwise Sequence lignment Evolutionary Basis Sequence Homology versus Sequence Similarity Sequence Similarity versus Sequence Identity Methods - cont Scoring Matrices Statistical Significance of Sequence lignment dapted from Brown and aragea, 7, with some slides from: ltman, Fernandez-Baca, Batzoglou, raven, Hunter, Page. BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 4 Methods Global and Local lignment lignment lgorithms Dot Matrix Method Dynamic Programming Method - cont Gap penalities DP for Global lignment DP for Local lignment Scoring Matrices mino acid scoring matrices PM BLOSUM omparisons between PM & BLOSUM Statistical Significance of Sequence lignment Dynamic Programming - 4 Steps:. Define score of optimal alignment, using recursion. Initialize and fill in a DP matrix for storing optimal scores of subproblems, by solving smallest subproblems first (bottom-up approach) 3. alculate score of optimal alignment(s) 4. race back through matrix to recover optimal alignment(s) that generated optimal score BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 5 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 6 BB 444/544 Fall 7 Dobbs

2 & BLS 9/7/7 Define: - Define Score of Optimal lignment using Recursion S(i, j) = Score of optimal alignment of x..i and y..j Initial conditions: x..i = Prefix of length i of x y.. j = Prefix of length j of y S(i,) = "i #$ S(, j) = " j #$ Recursive definition: For i N, j M: % S(i ", j ") +# (x i, y j ) ' S(i, j) = max& S(i ", j) "$ ' ( S(i, j ") "$ α = Match Reward β = Mismatch Penalty γ = Gap penalty σ(x i,y j ) = α or β γ = Gap penalty BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 7 - Initialize & Fill in DP Matrix for Storing Optimal Scores of Subproblems onstruct sequence vs sequence matrix Fill in from [,] to [N,M] (row by row), calculating best possible score for each alignment ending at residues at [i,j] N S(,)= M S(i,j) S(N,M) BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 8 How do we calculate S(i,j)? i.e., Score for alignment of x[..i] to y[..j]? of 3 cases optimal score for this subproblem: x i aligns to y j x i aligns to a gap y j aligns to a gap x x... x i- x i y y... y j- y j x x... x i- x i y y... y j x x... x i y y... y j- y j Specific Example: ase : Line up x i with y j i - i x: - G y: - j - j ase : Line up x i with space i - i x: - G - y: - - j Note: I changed sequences on this slide (to match the rest of DP example) Scoring onsequence? Match Bonus Space Penalty S(i-,j-) + σ(x i,y j ) S(i-,j) - γ S(i,j-) - γ ase 3: Line up y j with space i x: - G - y: - - j - j Space Penalty BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 9 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 α = Match Reward β = Mismatch Penalty γ = Gap penalty Ready? Fill in DP Matrix Keep track of dependencies of scores (in a pointer matrix) N S(,)= + σ(x i,y j ) = α or β M Initialization S(i,) = "i #$ S(, j) = " j #$ S(i-,j-) S(i,j-) - γ S(i-,j) S(i,j) S(N,M) Recursion % S(i ", j ") +# (x i, y j ) ' S(i, j) = max& S(i ", j) "$ ' ( S(i, j ") "$ BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 - γ Fill in the DP matrix!! G G for match, - for mismatch, -5 for space BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 BB 444/544 Fall 7 Dobbs

3 & BLS 9/7/7 3- alculate Score S(N,M) of Optimal lignment - for Global lignment G G + for match, - for mismatch, -5 for space 3- alculate Score S(N,M) of Optimal lignment - for Global lignment G G + for match, - for mismatch, -5 for space BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 3 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/ race back through matrix to recover optimal alignment(s) that generated the optimal score How? "Repeat" alignment calculations in reverse order, starting at from position with highest score and following path, position by position, back through matrix Result? Optimal alignment(s) of sequences raceback - for Global lignment Start in lower right corner & trace back to upper left Each arrow introduces one character at end of alignment: horizontal move puts a gap in left sequence vertical move puts a gap in top sequence diagonal move uses one character from each sequence BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 5 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 6 raceback to Recover lignment raceback to Recover lignment G G G G an have > optimal alignment; this example has Where did red arrows come from? BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 7 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 8 BB 444/544 Fall 7 Dobbs 3

4 & BLS 9/7/7 raceback to Recover lignment G G raceback to Recover lignment G G + for match, - for mismatch, -5 for space Where did 33 come from? Match =, so 33-= 3 Must have come from diagonal Where did 3 come from? (Not a match) Left? 8-5= 3; Diag? 3-= ; op? 8-5= 3 + for match, - for mismatch, -5 for space Where did 8 come from? wo possibilities: 3-5= 8 or -=8 hen, follow both paths BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 9 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 raceback to Recover lignment G G raceback to Recover lignment G G with - with with with - G with with with G with - with with - with with with G with - with with G with - with Great - but what are the alignments? # Great - but what are the alignments? # BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 What are the Global lignments with Optimal Score = 33? What are the Global lignments with Optimal Score = 33? op: G G Left: op: G G Left: : - G G : - G G - - : - G G : - G G - - horizontal move puts a gap in left sequence vertical move puts a gap in top sequence diagonal move uses one character from each sequence horizontal move puts a gap in left sequence vertical move puts a gap in top sequence diagonal move uses one character from each sequence BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 3 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 4 BB 444/544 Fall 7 Dobbs 4

5 & BLS 9/7/7 heck raceback? G G d v d h d d d h d h d BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 5 horizontal move puts a gap in left sequence vertical move puts a gap in top sequence diagonal move uses one character from each sequence Local lignment: Motivation o "ignore" stretches of non-coding DN: Non-coding regions (if "non-functional") are more likely to contain mutations than coding regions Local alignment between two protein-encoding sequences is likely to be between two exons o locate protein domains or motifs: Proteins with similar structures and/or similar functions but from different species (for example), often exhibit local sequence similarities Local sequence similarities may indicate functional modules Non-coding - "not encoding protein" Exons - "protein-encoding" parts of genes vs Introns = "intervening sequences" - segments of eukaryotic genes that "interrupt" exons Introns are transcribed into RN, but are later removed by RN processing & are not translated into protein BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 6 Local lignment: Example Local lignment: lgorithm G G G G G Match: + Mismatch or space: - S [i, j] = Score for optimally aligning a suffix of X with a suffix of Y Initialize top row & leftmost column of matrix with "" Best local alignment: G G G G G - Score = 5 Recall: for Global lignment, S [i, j] = Score for optimally aligning a prefix of X with a prefix of Y Initialize top row & leftmost column of with gap penalty BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 7 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 8 Filling in DP Matrix for Local lignment G G + for a match, - for a mismatch, -5 for a space raceback - for Local lignment G G + for a match, - for a mismatch, -5 for a space BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 9 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 3 BB 444/544 Fall 7 Dobbs 5

6 & BLS 9/7/7 : : 3: 4: What are the 4 Local lignments with Optimal Score =? G G G G G G G G G G Some Results re: lignment lgorithms (for oms, pre & Math types!) Most pairwise sequence alignment problems can be solved in O(mn) time Space requirement can be reduced to O(m+n), while keeping run-time fixed [Myers88] Highly similar sequences can be aligned in O (dn) time, where d measures the distance between the sequences [Landau86] BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 3 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 3 ffine Gap Penalty Functions Methods ffine Gap Penalties = Differential Gap Penalties used to reflect cost differences between opening a gap and extending an existing gap otal Gap Penalty is linear function of gap length: W = γ + δ X (k - ) where γ = gap opening penalty δ = gap extension penalty k = length of gap an also be solved in O(nm) time using DP Sometimes, a onstant Gap Penalty is used, but it is usually least realistic than the ffine Gap Penalty Global and Local lignment lignment lgorithms Dot Matrix Method Dynamic Programming Method - cont Gap penalities DP for Global lignment DP for Local lignment Scoring Matrices mino acid scoring matrices PM BLOSUM omparisons between PM & BLOSUM Statistical Significance of Sequence lignment BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 33 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 34 "Scoring" or "Substitution" Matrices Major types for mino cids: PM & BLOSUM PM = Point ccepted Mutation relies on "evolutionary model" based on observed differences in alignments of closely related proteins BLOSUM = BLOck SUbstitution Matrix based on % aa substitutions observed in blocks of conserved sequences within evolutionarily divergent proteins PM Matrix PM = Point ccepted Mutation relies on "evolutionary model" based on observed differences in closely related proteins Model includes defined rate for each type of sequence change Suffix number (n) reflects amount of "time" passed: rate of expected mutation if n% of amino acids had changed PM - for less divergent sequences (shorter time) PM5 - for more divergent sequences (longer time) BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 35 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 36 BB 444/544 Fall 7 Dobbs 6

& BLS 9/7/7 BLOSUM Matrix PM5 vs BLOSUM 6 BLOSUM = BLOck SUbstitution Matrix based on % aa substitutions observed in blocks of conserved sequences within evolutionarily divergent proteins Doesn't

7 & BLS 9/7/7 BLOSUM Matrix PM5 vs BLOSUM 6 BLOSUM = BLOck SUbstitution Matrix based on % aa substitutions observed in blocks of conserved sequences within evolutionarily divergent proteins Doesn't rely on a specific evolutionary model Suffix number (n) reflects expected similarity: average % aa identity in the MS from which the matrix was generated BLOSUM45 - for more divergent sequences BLOSUM6 - for less divergent sequences See ext Fig 3.5 = PM5 Fig 3.6= BLOSUM6 Usually only / of matrix is displayed (it is symmetric) Here: s(a,b) corresponds to score of aligning character a with character b BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 37 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 38 Which is Better? PM or BLOSUM PM matrices derived from evolutionary model often used in reconstructing phylogenetic trees - but, not very good for highly divergent sequences BLOSUM matrices based on direct observations more 'realistic" - and outperform PM matrices in terms of accuracy in local alignment Which ype of Matrix Should You Use? Several other types of matrices available: Gonnet & Jones-aylor-hornton: very robust in tree construction "Best" matrix depends on task: different matrices for different applications DVIE: if unsure, try several different matrices & choose the one that gives best alignment result BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 39 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 4 Sequence lignment Statistics Distribution of similarity scores in sequence alignment is not a simple "normal" distribution "Gumble extreme value distribution" - a highly skewed normal distribution with a long tail How ssess Statistical Significance of an lignment? ompare score of an alignment with distribution of scores of alignments for many 'randomized' (shuffled) versions of the original sequence If score is in extreme margin, then unlikely due to random chance P-value = probability that original alignment is due to random chance (lower P is better) P = sequences have clear homology P > - no better than random heck out: PRSS (Probability of Random Shuffles) BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 4 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 4 BB 444/544 Fall 7 Dobbs 7

8 & BLS 9/7/7 SEION II hp 4- Database Similarity Searching SEQUENE LIGNMEN Xiong: hp 4 Database Similarity Searching Unique Requirements of Database Searching Heuristic Database Searching Basic Local lignment Search ool (BLS) FS omparison of FS and BLS Database Searching with Smith-Waterman Method Exhaustive vs Heuristic Methods Exhaustive - tests every possible solution guaranteed to give best answer (identifies optimal solution) can be very time/space intensive! e.g., Dynamic Programming as in Smith-Waterman algorithm Heuristic - does NO test every possibility no guarantee that answer is best (but, often can identify optimal solution) sacrifices accuracy (potentially) for speed uses "rules of thumb" or "shortcuts" e.g., BLS & FS BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 43 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 44 SEPS: oday's Lab: focus on BLS Basic Local lignment Search ool. reate list of very possible "word" (e.g., 3- letters) from query sequence. Search database to identify sequences that contain matching words 3. Score match of word with sequence, using a substitution matrix 4. Extend match (seed) in both directions, while calculating alignment score at each step 5. ontinue extension until score drops below a threshold (due to mismatches) 6. ontiguous aligned segment pair (no gaps) is called: High Scoring Segment Pair (HSP) Lab3: focus on BLS Basic Local lignment Search ool BLS Results? Original version of BLS? List of HSPs = Maximum Scoring Pairs More recent, improved version of BLS? llows gaps: Gapped lignment How? llows score to drop below threshold, (but only temporarily) BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 45 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 46 BLS - a few details Developed by Stephen ultschul at NBI in 99 Word length? ypically: 3 aa for protein sequence nt for DN sequence Substitution matrix? Default is BLOSUM6 an change under lgorithm Parameters hoose other BLOSUM or PM matrices Stop-Extension hreshold? ypically: for proteins for DN BLS - Statistical Significance?. E-value: E = m x n x P m = total number of residues in database n = number of residues in query sequence P = probability that an HSP is result of random chance lower E-value, less likely to result from random change, thus higher significance. Bit Score: S' normalized score, to account for differences in sequence length & size of database 3. Low omplexity Masking remove repeats that confound scoring BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 47 BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 48 BB 444/544 Fall 7 Dobbs 8

9 & BLS 9/7/7 BLS - a Family of Programs: Several different BLS "flavors" BLSN - BLSP - BLSX - BLSN - BLSN - BB 444/544 F7 ISU Dobbs #8 - Finish DP, Scoring Matrices, Stats & BLS 9/7/7 49 BB 444/544 Fall 7 Dobbs 9

Global vs Local lignment - example Global alignment GGGG -G---G--G GGGG -GG-----G 1 = GGGG 2 = GGG Local alignment GGGG -GG-G---- Which is better? Glo

Global vs Local lignment - example Global alignment GGGG -G---G--G GGGG -GG-----G 1 = GGGG 2 = GGG Local alignment GGGG -GG-G---- Which is better? Glo BB 444/544 Lecture 7 Still more: Dynamic Programming Global vs Local lignment Scoring Matrices & lignment Statistics BLS #7_Sept5 Required Reading (before lecture) Last week: - for Lectures 4-7 Pairwise