生物资讯演算法-Lecture-8.ppt

生物資訊演算法Lecture8金城崇隆玟憲

Lecture8MoreaboutinexactmatchingDistance-KinexactmatchingPrimer-selectionproblemLongestincreasingsubsequenceApplicationtolongestcommonsubsequence

Distance-kinexactmatchingInputStringPonSandintegerkOutputIndicesjsuchthatP與某個S[i..j]之editdistance=kEx:S=000101000 P=11 k=1 output=4, 5, 6, 7twoalgorithm:(1)O(|P|*|S|)time(2)O(k|S|)time1234567891011010110110

想想outputindexj的條件P與某個S[i..j]的editdistance=kP與某個S[i..j]的similarity=-kP與某個S[i..j]的specialsimilarity=-k==01-00-1-11-10-1--1-1-1根據右表算出來bestalign的成績P開頭的gap不扣分情況下的bestalign的成績S1101001101101P---1110101ijP開頭不扣分是為了P能在S上滑動但是S前面塞gap要扣分

目標:要算P和S[1..j]之specialsimilarity?用dynamictableTT(i,j)=P[1..i]和S[1..j]之specialsimilarity00…….0-1-2xz….yT(i,j)-|P|PSij 1p[i]!=s[j] 0p[i]=s[j] x-D(i,j) y-1 z-1D(i,j)=T(i,j)=(Bysubstitutionmatrix)

Algorithm(1)1.填完dynamictable2.foreachj=1to|S| ifT(|P|,j)=-kthenoutputj;(找lastrow即可)Time:O(|P||S))Space:O(|P|＋|S|)

如何由j找i1.由T(|P|,j)在表格中往回走2.走到第一個row就停止3.然後就可以找到對應的ITimeforeachj:O(|P|)Timeforallindicesj:O(|P||S|)Spaceforallindicesj:O(|P||S|)?如何將space降到O(|S|)回推時不可能無限往左走,最多往左走k步,而kp所以是O(|P|)

希望改進目標:time與space均降到O(k|S|)Trick: 由editdistance為d的O(|S|)條path推知editdistance為d+1的O(|S|)的path

DEF =1.由row0開始2.止於jthdiagonal3.path上每個格子的specialsimilarity均=-d (editdistance=d)觀察表格中有某條(d,j)-path其末端止於rowIIffP[1..I]和S[1..j+i]的specialsimilarity=-d(d,j)path

Algorithm(2)foreachj=-|P|to|S| if某條(k,j)-path的末端止於row|P| thenoutputj+|P|;因為-|P|=j=|S|

R(d,j)?所有(d,j)－path所有reach之最低(大)的RowNumber。i=R(d,j)觀察:?(1)某條path止於rowi(2)所有(d,j)path都構不著rowi+1定義:-d-d-1ijj+i而且一定是且P[I+1]?S[j+i+1]Q：why?Ans:如果比-d還大時，即可再往下延伸一格。

KeyPropertyR(d+1,j)=i*R(d+1,j)=i1，andP[i1+2...i*]=S[i1+j+2...i*+j]R(d,j+1)=i2，andP[i2+2.