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

1/55,回顾,DynamicProgrammingEditDistance（编辑距离）Alignment（比对）DirectedAcyclicGraphEditGraphBacktracking,-TGCAT-A-C,AT-C-TGATC,2/55,习题,4，求两条序列的最长共同子序列。【作业】,v=TACGGGTAT,w=GGACGTACG,3/55,G,G,A,C,G,T,A,C,G,T,A,C,G,G,G,T,A,T,4,SequenceAlignment,5/55,Outline,GlobalAlignmentScoringMatricesLocalAlignmentAlignmentwithAffineGapPenalties,6/55,FromLCStoAlignment:ChangeuptheScoring,TheLongestCommonSubsequence(LCS)problemthesimplestformofsequencealignmentallowsonlyinsertionsanddeletions(nomismatches).IntheLCSProblem,wescored1formatchesand0forindelsConsiderpenalizingindelsandmismatcheswithnegativescoresSimplestscoringschema:+1:matchpremium-:mismatchpenalty-:indelpenalty,-TGCAT-A-C,AT-C-TGATC,7/55,SimpleScoring,Whenmismatchesarepenalizedby,indelsarepenalizedby,andmatchesarerewardedwith+1,theresultingscoreis:#matches(#mismatches)(#indels),8/55,TheGlobalAlignmentProblem,FindthebestalignmentbetweentwostringsunderagivenscoringschemaInput:StringsvandwandascoringschemaOutput:Alignmentofmaximumscore,m:mismatchpenalty:indelpenalty,9/55,ScoringMatrices,Togeneralizescoring,considera(4+1)x(4+1)scoringmatrix.Inthecaseofanaminoacidsequencealignment,thescoringmatrixwouldbea(20+1)x(20+1)size.Theadditionof1istoincludethescoreforcomparisonofagapcharacter“-”.Thiswillsimplifythealgorithmasfollows:,10/55,TheBlosum62ScoringMatrix,11/55,MeasuringSimilarity,MeasuringtheextentofsimilaritybetweentwosequencesBasedonpercentsequenceidentityBasedonconservation,12/55,PercentSequenceIdentity,Theextenttowhichtwonucleotideoraminoacidsequencesareinvariant,ACCTGAGAGACGTGGCAG,70%identical,mismatch,indel,13/55,MakingaScoringMatrix,Scoringmatricesarecreatedbasedonbiologicalevidence.Alignmentscanbethoughtofastwosequencesthatdifferduetomutations.Someofthesemutationshavelittleeffectontheproteinsfunction,thereforesomepenalties,(vi,wj),willbelessharshthanothers.,14/55,ScoringMatrix:Example,NoticethatalthoughRandKaredifferentaminoacids,theyhaveapositivescore.Why?Theyarebothpositivelychargedaminoacidswillnotgreatlychangefunctionofprotein.,15/55,Conservation,Aminoacidchangesthattendtopreservethephysico-chemicalpropertiesoftheoriginalresiduePolartopolaraspartateglutamateNonpolartononpolaralaninevalineSimilarlybehavingresiduesleucinetoisoleucine,16/55,Scoringmatrices,AminoacidsubstitutionmatricesPAMBLOSUMDNAsubstitutionmatricesDNAislessconservedthanproteinsequencesLesseffectivetocomparecodingregionsatnucleotidelevel,17/55,PAM,PointAcceptedMutation(Dayhoffetal.)1PAM=PAM1=1%averagechangeofallaminoacidpositionsAfter100PAMsofevolution,noteveryresiduewillhavechangedsomeresiduesmayhavemutatedseveraltimessomeresiduesmayhavereturnedtotheiroriginalstatesomeresiduesmaynotchangedatall,18/55,PAMX,PAMx=PAM1xPAM250=PAM1250PAM250isawidelyusedscoringmatrix:,AlaArgAsnAspCysGlnGluGlyHisIleLeuLys.ARNDCQEGHILK.AlaA13699589126867.ArgR3174325326329AsnN446725646325AspD54811171056325CysC2111521122211GlnQ3556110737235.TrpW020000001010TyrY112131113221ValV74444444541510,19/55,BLOSUM,BlocksSubstitutionMatrixScoresderivedfromobservationsofthefrequenciesofsubstitutionsinblocksoflocalalignmentsinrelatedproteinsMatrixnameindicatesevolutionarydistanceBLOSUM62wascreatedusingsequencessharingnomorethan62%identity,20/55,TheBlosum62ScoringMatrix,BLOSUM62,21/55,相似度越低的序列，在比对的时候，采用PAM矩阵时，后面的数字越大，采用BLOSUM矩阵时，后面的数字越小。,22/55,Localvs.GlobalAlignment,TheGlobalAlignmentProblemtriestofindthelongestpathbetweenvertices(0,0)and(n,m)intheeditgraph.TheLocalAlignmentProblemtriestofindthelongestpathamongpathsbetweenarbitraryvertices(i,j)and(i,j)intheeditgraph.,23/55,Localvs.GlobalAlignment,TheGlobalAlignmentProblemtriestofindthelongestpathbetweenvertices(0,0)and(n,m)intheeditgraph.TheLocalAlignmentProblemtriestofindthelongestpathamongpathsbetweenarbitraryvertices(i,j)and(i,j)intheeditgraph.Intheeditgraphwithnegatively-scorededges,LocalAlignmetmayscorehigherthanGlobalAlignment,24/55,Localvs.GlobalAlignment(contd),GlobalAlignmentLocalAlignmentbetteralignmenttofindconservedsegment,-T-CC-C-AGT-TATGT-CAGGGGACACGA-GCATGCAGA-GAC,|,AATTGCCGCC-GTCGT-T-TTCAG-CA-GTTATGT-CAGAT-C,tccCAGTTATGTCAGgggacacgagcatgcagagac,|,aattgccgccgtcgttttcagCAGTTATGTCAGatc,25/55,LocalAlignment:Example,Globalalignment,Localalignment,26/55,LocalAlignments:Why?,Twogenesindifferentspeciesmaybesimilarovershortconservedregionsanddissimilaroverremainingregions.Example:Homeoboxgeneshaveashortregioncalledthehomeodomainthatishighlyconservedbetweenspecies.AglobalalignmentwouldnotfindthehomeodomainbecauseitwouldtrytoaligntheENTIREsequence,27/55,TheLocalAlignmentProblem,Goal:FindthebestlocalalignmentbetweentwostringsInput:Stringsv,wandscoringmatrixOutput:Alignmentofsubstringsofvandwwhosealignmentscoreismaximumamongallpossiblealignmentofallpossiblesubstrings,28/55,TheProblemwiththisProblem,LongruntimeO(n4):-Inthegridofsizenxntherearen2vertices(i,j)thatmayserveasasource.-Foreachsuchvertexcomputingalignmentsfrom(i,j)to(i,j)takesO(n2)time.Thiscanberemediedbygivingfreerides,29/55,LocalAlignment:Example,Globalalignment,Localalignment,30/55,LocalAlignment:Example,31/55,LocalAlignment:Example,32/55,LocalAlignment:Example,33/55,LocalAlignment:Example,34/55,LocalAlignment:Example,35/55,LocalAlignment:RunningTime,LongruntimeO(n4):-Inthegridofsizenxntherearen2vertices(i,j)thatmayserveasasource.-Foreachsuchvertexcomputingalignmentsfrom(i,j)to(i,j)takesO(n2)time.Thiscanberemediedbygivingfreerides,36/55,LocalAlignment:FreeRides,Vertex(0,0),Thedashededgesrepresentthefreeridesfrom(0,0)toeveryothernode.,Yeah,afreeride!,37/55,TheLocalAlignmentRecurrence,Thelargestvalueofsi,joverthewholeeditgraphisthescoreofthebestlocalalignment.Therecurrence:,0si,j=maxsi-1,j-1+(vi,wj)si-1,j+(vi,-)si,j-1+(-,wj),38/55,TheLocalAlignmentRecurrence,Thelargestvalueofsi,joverthewholeeditgraphisthescoreofthebestlocalalignment.Therecurrence:,0si,j=maxsi-1,j-1+(vi,wj)si-1,j+(vi,-)si,j-1+(-,wj),39/55,/Blast.cgiNP_006735NP_000945,40/55,41/55,习题,考虑序列v=TACGGGTAT和w=GGACGTACG。假设匹配奖励+1，错配和插缺罚分均为-1.【作业】填写序列v和w之间的全局联配的动态规划表（编辑图或相似度矩阵）。在各单元画出箭头以存储返回信息。全局最优联配的得分是多少？这个得分对应的联配又是什么？填写序列v和w之间的局部联配的动态规划表。在各单元画出箭头以存储返回信息。在这种情形下，局部最优联配的得分是多少？这个得分对应的联配又是什么？,42/55,G,G,A,C,G,T,A,C,G,T,A,C,G,G,G,T,A,T,全局比对,43/55,局部比对,G,G,A,C,G,T,A,C,G,T,A,C,G,G,G,T,A,T,44/55,ScoringIndels:NaiveApproach,Afixedpenaltyisgiventoeveryindel:-for1indel,-2for2consecutiveindels-3for3consecutiveindels,etc.Canbetooseverepenaltyforaseriesof100consecutiveindels,45/55,AffineGapPenalties,Innature,aseriesofkindelsoftencomeasasingleeventratherthanaseriesofksinglenucleotideevents:,ATA_GCATATTGC,ATAG_GCAT_GTGC,Normalscoringwouldgivethesamescoreforbothalignments,46/55,AccountingforGaps,Gaps-contiguoussequenceofspacesinoneoftherowsScoreforagapoflengthxis:-(+x)where0isthepenaltyforintroducingagap:gapopeningpenaltywillbelargerelativeto:gapextensionpenaltybecauseyoudonotwanttoaddtoomuchofapenaltyforextendingthegap.,47/55,AffineGapPenalties,Gappenalties:-whenthereis1indel-2whenthereare2indels-3whenthereare3indels,etc.-x(-gapopening-xgapextensions)Somehowreducedpenalties(ascomparedtonavescoring)aregiventorunsofhorizontalandverticaledges,48/55,AffineGapPenaltiesandEditGraph,Toreflectaffinegappenaltieswehavetoadd“long”horizontalandverticaledgestotheeditgraph.Eachsuchedgeoflengthxshouldhaveweight-x*,49/55,Adding“AffinePenalty”EdgestotheEditGraph,Therearemanysuchedges!Addingthemtothegraphincreasestherunningtimeofthealignmentalgorithmbyafactorofn(wherenisthenumberofvertices)SothecomplexityincreasesfromO(n2)toO(n3),50/55,Manhattanin3Layers,51/55,AffineGapPenaltiesand3LayerManhattanGrid,Thethreerecurrencesforthescoringalgorithmcreatesa3-layeredgraph.Thetoplevelcreates/extendsgapsinthesequencew.Thebottomlevelcreates/extendsgapsinsequencev.Themiddlelevelextendsmatchesandmismatches.,52/55,Sw