动态规划法——双序列比对.ppt

《动态规划法——双序列比对.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1/55回顾DynamicProgrammingEditDistance（编辑距离）Alignment（比对）DirectedAcyclicGraphEditGraphBacktracking-TGCAT-A-CAT-C-TGATC2/55习题4，求两条序列的最长共同子序列。【作业】v=TACGGGTATw=GGACGTACG3/550123456789000000000001020304050607080905GGACGTACGTACGGGTAT4SequenceAlignment5/55OutlineGl

2、obalAlignmentScoringMatricesLocalAlignmentAlignmentwithAffineGapPenalties6/55FromLCStoAlignment:ChangeuptheScoringTheLongestCommonSubsequence(LCS)problem—thesimplestformofsequencealignment–allowsonlyinsertionsanddeletions(nomismatches).IntheLCSProblem,wesco

3、red1formatchesand0forindelsConsiderpenalizingindelsandmismatcheswithnegativescoresSimplestscoringschema:+1:matchpremium-μ:mismatchpenalty-σ:indelpenalty-TGCAT-A-CAT-C-TGATCAKRANRKAAANK-1+(-1)+(-2)+5+7+3=117/55SimpleScoringWhenmismatchesarepenalizedby–μ,inde

4、lsarepenalizedby–σ,andmatchesarerewardedwith+1,theresultingscoreis:#matches–μ(#mismatches)–σ(#indels)8/55TheGlobalAlignmentProblemFindthebestalignmentbetweentwostringsunderagivenscoringschemaInput:StringsvandwandascoringschemaOutput:Alignmentofmaximumscorem

5、:mismatchpenaltyσ:indelpenalty9/55ScoringMatricesTogeneralizescoring,considera(4+1)x(4+1)scoringmatrixδ.Inthecaseofanaminoacidsequencealignment,thescoringmatrixwouldbea(20+1)x(20+1)size.Theadditionof1istoincludethescoreforcomparisonofagapcharacter“-”.Thiswi

6、llsimplifythealgorithmasfollows:10/55TheBlosum62ScoringMatrix11/55MeasuringSimilarityMeasuringtheextentofsimilaritybetweentwosequencesBasedonpercentsequenceidentityBasedonconservation12/55PercentSequenceIdentityTheextenttowhichtwonucleotideoraminoacidsequen

7、cesareinvariantACCTGAG–AGACGTG–GCAG70%identicalmismatchindel13/55MakingaScoringMatrixScoringmatricesarecreatedbasedonbiologicalevidence.Alignmentscanbethoughtofastwosequencesthatdifferduetomutations.Someofthesemutationshavelittleeffectontheprotein’sfunction

8、,thereforesomepenalties,δ(vi,wj),willbelessharshthanothers.14/55ScoringMatrix:ExampleAKRANRKAAANK-1+(-1)+(-2)+5+7+3=11ARNKA5-2-1-1R-7-13N--70K---6NoticethatalthoughRandKaredifferentaminoacids,theyhavea