L3: Blast: Local Alignment and other flavorsAn ExampleSequence AlignmentAn O(nm) algorithm for score computationBase case (Initialization)A tableaux approachAlignment TableSlide 8Computing Optimum AlignmentComputing Optimal AlignmentsRetrieving Opt.AlignmentSlide 12Algorithm to retrieve optimal alignmentSummaryGlobal versus Local AlignmentBlast Outputs Local AlignmentLocal AlignmentSlide 18Slide 19Local Alignment Trick (Smith-Waterman algorithm)Generalizing Gap CostUsing affine gap penaltiesAffine gap penaltiesO(nm) solution for affine gap costsAlignment Space?Alignment (Linear Space)Linear Space AlignmentLinear Space (cont’d)Backward alignmentForward, Backward computationSlide 31Linear Space complexitySlide 33Blast and local alignmentLarge database searchWhy is Blast Fast?Silly Question!ObservationsBasic probabilityBasic Probability:ExpectationExpected number of matchesExpected number of exact Matches is small!Observation 2Why is this important?Just the FactsBLASTWhy is BLAST fast?Keyword MatchingRelated notesP-value computationZ-scores for alignmentBlast E-valueExponential distributionPowerPoint PresentationSlide 55Blast VariantsSlide 57Slide 58Fa05 CSE 182L3: Blast: Local Alignment and other flavorsFa05 CSE 182An Example•Align s=TCAT with t=TGCAA•Match Score = 1•Mismatch score = -1, Indel Score = -1•Score A1?, Score A2? T C A T -T G C A AT C A TT G C A AA1A2Fa05 CSE 182Sequence Alignment•Recall: Instead of computing the optimum alignment, we are computing the score of the optimum alignment•Let S[i,j] denote the score of the optimum alignment of the prefix s[1..i] and t [1..j]Fa05 CSE 182An O(nm) algorithm for score computation•The iteration ensures that all values on the right are computed in earlier steps.€ S[i, j] = maxS[i −1, j −1] + C(si,tj)S[i −1, j] + C(si,−)S[i, j −1] + C(−,tj) ⎧ ⎨ ⎪ ⎩ ⎪For i = 1 to n For j = 1 to mFa05 CSE 182Base case (Initialization)€ S[0,0] = 0S[i,0] = C(si,−) + S[i −1,0] ∀iS[0, j] = C(−,sj) + S[0, j −1] ∀jFa05 CSE 182A tableaux approachsn1i1 j n € MS[i,j-1] S[i,j]S[i-1,j]S[i-1,j-1]tCell (i,j) contains the score S[i,j]. Each cell only looks at 3 neighboring cells€ S[i, j] = maxS[i −1, j −1] + C(si,tj)S[i −1, j] + C(si,−)S[i, j −1] + C(−,tj) ⎧ ⎨ ⎪ ⎩ ⎪Fa05 CSE 182 0 -1 -2 -3 -4 -5 -1 1 0 -1 -2 -3 -2 0 0 1 0 -1 -3 -1 -1 0 2 1 -4 -2 -2 -1 1 1T G C A ATCATAlignment TableFa05 CSE 182 1 1 -1 -2 -2 -4 1 2 0 -1 -1 -3 -1 0 1 0 0 -2 -3 -2 -1 0 1 -1 -5 -4 -3 -2 -1 0T G C A ATCATAlignment Table•S[4,5] = 1 is the score of an optimum alignment•Therefore, A2 is an optimum alignment•We know how to obtain the optimum Score. How do we get the best alignment?Fa05 CSE 182Computing Optimum Alignment•At each cell, we have 3 choices•We maintain additional information to record the choice at each step.For i = 1 to n For j = 1 to m € S[i, j] = maxS[i −1, j −1] + C(si,tj)S[i −1, j] + C(si,−)S[i, j −1] + C(−,tj) ⎧ ⎨ ⎪ ⎩ ⎪ If (S[i,j]= S[i-1,j-1] + C(si,tj)) M[i,j] = If (S[i,j]= S[i-1,j] + C(si,-)) M[i,j] = If (S[i,j]= S[i,j-1] + C(-,tj) ) M[i,j] = j-1i-1jiFa05 CSE 182T G C A ATCAT 1 1 -1 -2 -2 -4 1 2 0 -1 -1 -3 -1 0 1 0 0 -2 -3 -2 -1 0 1 -1 -5 -4 -3 -2 -1 0Computing Optimal AlignmentsFa05 CSE 182Retrieving Opt.Alignment 1 1 -1 -2 -2 -4 1 2 0 -1 -1 -3 -1 0 1 0 0 -2 -3 -2 -1 0 1 -1 -5 -4 -3 -2 -1 0T G C A ATCAT•M[4,5]= Implies that S[4,5]=S[3,4]+C(A,T) orATM[3,4]= Implies that S[3,4]=S[2,3] +C(A,A) orATAA1 2 3 4 51324Fa05 CSE 182Retrieving Opt.Alignment 1 1 -1 -2 -2 -4 1 2 0 -1 -1 -3 -1 0 1 0 0 -2 -3 -2 -1 0 1 -1 -5 -4 -3 -2 -1 0T G C A ATCAT•M[2,3]= Implies that S[2,3]=S[1,2]+C(C,C) orATM[1,2]= Implies that S[1,2]=S[1,1] +C(-,G) orATAAAACCCC-GTT1 2 3 4 51324Fa05 CSE 182Algorithm to retrieve optimal alignmentRetrieveAl(i,j)if (M[i,j] == `\’) return (RetrieveAl (i-1,j-1) . ) else if (M[i,j] == `|’) return (RetrieveAl (i-1,j) . )sitjsi--tjelse if (M[i,j] == `--’)else if (M[i,j] == `--’) return (RetrieveAl (i,j-1) . return (RetrieveAl (i,j-1) . ))Fa05 CSE 182Summary•An optimal alignment of strings of length n and m can be computed in O(nm) time•There is a tight connection between computation of optimal score, and computation of opt. Alignment–True for all DP based solutionsFa05 CSE 182Global versus Local AlignmentConsider s = ACCACCCCTT t = ATCCCCACATACCACCCCTTACCACCCCTTA TCCCCACATA TCCCCACATATCCCCACATATCCCCACATACCACCCCT TACCACCCCT TFa05 CSE 182Blast Outputs Local Alignmentquery2619 405422SchematicdbFa05 CSE 182Local Alignment•Compute maximum scoring interval over all sub-intervals (a,b), and (a’,b’)•How can we compute this efficiently?aba’ b’Fa05 CSE 182Local Alignment•Recall that in global alignment, we compute the best score for all prefix pairs s(1..i) and t(1..j).•Instead, compute the best score for all sub-alignments that end in s(i) and t(j).•What changes in the recurrence? aia’ jFa05 CSE 182Local Alignment•The original recurrence still works, except when the optimum score S[i,j] is negative•When S[i,j] <0, it means that the optimum local alignment cannot include the point (i,j).•So, we must reset the score to 0.ii-1jj-1sitjFa05 CSE 182Local Alignment Trick (Smith-Waterman algorithm)€ S[i, j] = max0S[i −1, j −1] + C(si,tj)S[i −1, j] + C(si,−)S[i, j −1] + C(−,tj) ⎧ ⎨ ⎪ ⎩ ⎪How can we compute the local alignment itself?Fa05 CSE 182Generalizing Gap Cost•It is more likely for gaps to be contiguous•The penalty for a gap of length l should be€ go + ge ∗ lFa05 CSE 182Using affine gap penalties€ S[i, j] = maxl0S[i −1, j −1] + C(si,tj)S[i − l, j] + go + ge * lS[i, j − l] + go + ge * l ⎧ ⎨ ⎪ ⎩ ⎪•What is the time taken for this?•What are the values that l can take?•Can we get rid of the extra Dimension?Fa05 CSE