动态规划法双序列比对

动态规划法双序列比对第1页，共55页，2023年，2月20日，星期日2

/55习题4，求两条序列的最长共同子序列。【作业】v=TACGGGTATw=GGACGTACG第2页，共55页，2023年，2月20日，星期日3

/550123456789000000000001020304050607080905GGACGTACGTACGGGTAT第3页，共55页，2023年，2月20日，星期日4SequenceAlignment第4页，共55页，2023年，2月20日，星期日5

/55OutlineGlobalAlignmentScoringMatricesLocalAlignmentAlignmentwithAffineGapPenalties第5页，共55页，2023年，2月20日，星期日6

/55FromLCStoAlignment:ChangeuptheScoringTheLongestCommonSubsequence(LCS)problem—thesimplestformofsequencealignment–allowsonlyinsertionsanddeletions(nomismatches).IntheLCSProblem,wescored1formatchesand0forindelsConsiderpenalizingindelsandmismatcheswithnegativescoresSimplestscoringschema:

+1:matchpremium

-μ:mismatchpenalty

-σ:indelpenalty-TGCAT-A-CAT-C-TGATCAKRANRKAAANK-1+(-1)+(-2)+5+7+3=11第6页，共55页，2023年，2月20日，星期日7

/55SimpleScoringWhenmismatchesarepenalizedby–μ,indelsarepenalizedby–σ,andmatchesarerewardedwith+1,theresultingscoreis:#matches–μ(#mismatches)–σ(#indels)第7页，共55页，2023年，2月20日，星期日8

/55TheGlobalAlignmentProblemFindthebestalignmentbetweentwostringsunderagivenscoringschemaInput:StringsvandwandascoringschemaOutput:Alignmentofmaximumscorem:mismatchpenaltyσ:indelpenalty第8页，共55页，2023年，2月20日，星期日9

/55ScoringMatricesTogeneralizescoring,considera(4+1)x(4+1)scoringmatrixδ.Inthecaseofanaminoacidsequencealignment,thescoringmatrixwouldbea(20+1)x(20+1)size.Theadditionof1istoincludethescoreforcomparisonofagapcharacter“-”.Thiswillsimplifythealgorithmasfollows:第9页，共55页，2023年，2月20日，星期日10

/55TheBlosum62ScoringMatrix第10页，共55页，2023年，2月20日，星期日11

/55MeasuringSimilarityMeasuringtheextentofsimilaritybetweentwosequencesBasedonpercentsequenceidentityBasedonconservation第11页，共55页，2023年，2月20日，星期日12

/55PercentSequenceIdentityTheextenttowhichtwonucleotideoraminoacidsequencesareinvariantACCTGAG–AGACGTG–GCAG70%identicalmismatchindel第12页，共55页，2023年，2月20日，星期日13

/55MakingaScoringMatrixScoringmatricesarecreatedbasedonbiologicalevidence.Alignmentscanbethoughtofastwosequencesthatdifferduetomutations.Someofthesemutationshavelittleeffectontheprotein’sfunction,thereforesomepenalties,δ(vi,wj),willbelessharshthanothers.第13页，共55页，2023年，2月20日，星期日14

/55ScoringMatrix:ExampleAKRANRKAAANK-1+(-1)+(-2)+5+7+3=11ARNKA5-2-1-1R-7-13N--70K---6NoticethatalthoughRandKaredifferentaminoacids,theyhaveapositivescore.Why?Theyarebothpositivelychargedaminoacidswillnotgreatlychangefunctionofprotein.第14页，共55页，2023年，2月20日，星期日15

/55ConservationAminoacidchangesthattendtopreservethephysico-chemicalpropertiesoftheoriginalresiduePolartopolaraspartateglutamateNonpolartononpolaralaninevalineSimilarlybehavingresiduesleucinetoisoleucine第15页，共55页，2023年，2月20日，星期日16

/55ScoringmatricesAminoacidsubstitutionmatricesPAMBLOSUMDNAsubstitutionmatricesDNAislessconservedthanproteinsequencesLesseffectivetocomparecodingregionsatnucleotidelevel第16页，共55页，2023年，2月20日，星期日17

/55PAMPointAcceptedMutation(Dayhoffetal.)1PAM=PAM1=1%averagechangeofallaminoacidpositionsAfter100PAMsofevolution,noteveryresiduewillhavechangedsomeresiduesmayhavemutatedseveraltimessomeresiduesmayhavereturnedtotheiroriginalstatesomeresiduesmaynotchangedatall第17页，共55页，2023年，2月20日，星期日18

/55PAMXPAMx=PAM1xPAM250=PAM1250PAM250isawidelyusedscoringmatrix:

AlaArgAsnAspCysGlnGluGlyHisIleLeuLys...ARNDCQEGHILK...AlaA13699589126867...ArgR3174325326329AsnN446725646325AspD54811171056325CysC2111521122211GlnQ3556110737235...TrpW020000001010TyrY112131113221ValV74444444541510第18页，共55页，2023年，2月20日，星期日19

/55BLOSUMBlocksSubstitutionMatrixScoresderivedfromobservationsofthefrequenciesofsubstitutionsinblocksoflocalalignmentsinrelatedproteinsMatrixnameindicatesevolutionarydistanceBLOSUM62wascreatedusingsequencessharingnomorethan62%identity第19页，共55页，2023年，2月20日，星期日20

/55TheBlosum62ScoringMatrixBLOSUM62第20页，共55页，2023年，2月20日，星期日21

/55BLOSUM90PAM30低趋异度小鼠和大鼠RBPBLOSUM45PAM240高趋异度小鼠和细菌的lipocalinBLOSUM80PAM120BLOSUM62PAM180相似度越低的序列，在比对的时候，采用PAM矩阵时，后面的数字越大，采用BLOSUM矩阵时，后面的数字越小。第21页，共55页，2023年，2月20日，星期日22

/55Localvs.GlobalAlignmentTheGlobalAlignmentProblemtriestofindthelongestpathbetweenvertices(0,0)and(n,m)intheeditgraph.TheLocalAlignmentProblemtriestofindthelongestpathamongpathsbetweenarbitraryvertices(i,j)and(i’,j’)intheeditgraph.第22页，共55页，2023年，2月20日，星期日23

/55Localvs.GlobalAlignmentTheGlobalAlignmentProblemtriestofindthelongestpathbetweenvertices(0,0)and(n,m)intheeditgraph.TheLocalAlignmentProblemtriestofindthelongestpathamongpathsbetweenarbitraryvertices(i,j)and(i’,j’)intheeditgraph.Intheeditgraphwithnegatively-scorededges,LocalAlignmetmayscorehigherthanGlobalAlignment第23页，共55页，2023年，2月20日，星期日24

/55Localvs.GlobalAlignment(cont’d)GlobalAlignmentLocalAlignment—betteralignmenttofindconservedsegment--T—-CC-C-AGT—-TATGT-CAGGGGACACG—A-GCATGCAGA-GAC|||||||||||||||||||||||AATTGCCGCC-GTCGT-T-TTCAG----CA-GTTATG—T-CAGAT--CtccCAGTTATGTCAGgggacacgagcatgcagagac||||||||||||aattgccgccgtcgttttcagCAGTTATGTCAGatc第24页，共55页，2023年，2月20日，星期日25

/55LocalAlignment:ExampleGlobalalignmentLocalalignmentComputea“mini”GlobalAlignmenttogetLocal第25页，共55页，2023年，2月20日，星期日26

/55LocalAlignments:Why?Twogenesindifferentspeciesmaybesimilarovershortconservedregionsanddissimilaroverremainingregions.Example:Homeoboxgeneshaveashortregioncalledthehomeodomainthatishighlyconservedbetweenspecies.AglobalalignmentwouldnotfindthehomeodomainbecauseitwouldtrytoaligntheENTIREsequence第26页，共55页，2023年，2月20日，星期日27

/55TheLocalAlignmentProblemGoal:FindthebestlocalalignmentbetweentwostringsInput:Stringsv,wandscoringmatrixδOutput:Alignmentofsubstringsofvandwwhosealignmentscoreismaximumamongallpossiblealignmentofallpossiblesubstrings第27页，共55页，2023年，2月20日，星期日28

/55TheProblemwiththisProblemLongruntimeO(n4):-Inthegridofsizenxnthereare~n2vertices(i,j)thatmayserveasasource.

-Foreachsuchvertexcomputingalignmentsfrom(i,j)to(i’,j’)takesO(n2)time.Thiscanberemediedbygivingfreerides第28页，共55页，2023年，2月20日，星期日29

/55LocalAlignment:ExampleGlobalalignmentLocalalignmentComputea“mini”GlobalAlignmenttogetLocal第29页，共55页，2023年，2月20日，星期日30

/55LocalAlignment:Example第30页，共55页，2023年，2月20日，星期日31

/55LocalAlignment:Example第31页，共55页，2023年，2月20日，星期日32

/55LocalAlignment:Example第32页，共55页，2023年，2月20日，星期日33

/55LocalAlignment:Example第33页，共55页，2023年，2月20日，星期日34

/55LocalAlignment:Example第34页，共55页，2023年，2月20日，星期日35

/55LocalAlignment:RunningTimeLongruntimeO(n4):-Inthegridofsizenxnthereare~n2vertices(i,j)thatmayserveasasource.

-Foreachsuchvertexcomputingalignmentsfrom(i,j)to(i’,j’)takesO(n2)time.Thiscanberemediedbygivingfreerides第35页，共55页，2023年，2月20日，星期日36

/55LocalAlignment:FreeRidesVertex(0,0)Thedashededgesrepresentthefreeridesfrom(0,0)toeveryothernode.Yeah,afreeride!第36页，共55页，2023年，2月20日，星期日37

/55TheLocalAlignmentRecurrenceThelargestvalueofsi,joverthewholeeditgraphisthescoreofthebestlocalalignment.Therecurrence:0si,j=maxsi-1,j-1+δ

(vi,wj)si-1,j+δ

(vi,-)

si,j-1+δ

(-,wj){NoticethereisonlythischangefromtheoriginalrecurrenceofaGlobalAlignment第37页，共55页，2023年，2月20日，星期日38

/55TheLocalAlignmentRecurrenceThelargestvalueofsi,joverthewholeeditgraphisthescoreofthebestlocalalignment.Therecurrence:0si,j=maxsi-1,j-1+δ

(vi,wj)si-1,j+δ

(vi,-)

si,j-1+δ

(-,wj){PowerofZERO:thereisonlythischangefromtheoriginalrecurrenceofaGlobalAlignment-sincethereisonlyone“freeride”edgeenteringintoeveryvertex第38页，共55页，2023年，2月20日，星期日39

/55/Blast.cgi

NP_006735NP_000945第39页，共55页，2023年，2月20日，星期日40

/55第40页，共55页，2023年，2月20日，星期日41

/55习题考虑序列v=TACGGGTAT和w=GGACGTACG。假设匹配奖励+1，错配和插缺罚分均为-1.【作业】填写序列v和w之间的全局联配的动态规划表（编辑图或相似度矩阵）。在各单元画出箭头以存储返回信息。全局最优联配的得分是多少？这个得分对应的联配又是什么？填写序列v和w之间的局部联配的动态规划表。在各单元画出箭头以存储返回信息。在这种情形下，局部最优联配的得分是多少？这个得分对应的联配又是什么？第41页，共55页，2023年，2月20日，星期日42

/55-012345678900-1-2-3-4-5-6-7-8-91-12-23-34-45-56-67-78-899GGACGTACGTACGGGTAT全局比对第42页，共55页，2023年，2月20日，星期日43

/55局部比对-012345678900000000000102030405060708090GGACGTACGTACGGGTAT第43页，共55页，2023年，2月20日，星期日44

/55ScoringIndels:NaiveApproachAfixedpenaltyσ

isgiventoeveryindel:-σfor1indel,-2σfor2consecutiveindels-3σfor3consecutiveindels,etc.Canbetooseverepenaltyforaseriesof100consecutiveindels第44页，共55页，2023年，2月20日，星期日45

/55AffineGapPenaltiesInnature,aseriesofkindelsoftencomeasasingleeventratherthanaseriesofksinglenucleotideevents:ATA__GCATATTGCATAG_GCAT_GTGCNormalscoringwouldgivethesamescoreforbothalignmentsThisismorelikely.Thisislesslikely.第45页，共55页，2023年，2月20日，星期日46

/55AccountingforGapsGaps-contiguoussequenceofspacesinoneoftherowsScoreforagapoflengthxis:-(ρ+

σx)whereρ>0isthepenaltyforintroducingagap:gapopeningpenalty

ρwillbelargerelativetoσ:

gapextensionpenaltybecauseyoudonotwanttoaddtoomuchofapenaltyforextendingthegap.第46页，共55页，2023年，2月20日，星期日47

/55AffineGapPenaltiesGappenalties:-ρ-σwhenthereis1indel-ρ-2σwhenthereare2indels-ρ-3σwhenthereare3indels,etc.-ρ-x·σ(-gapopening-xgapextensions)Somehowreducedpenalties(ascomparedtonaïvescoring)aregiventorunsofhorizontalandverticaledges第47页，共55页，2023年，2月20日，星期日48

/55AffineGapPenaltiesandEditGraphToreflectaffinegappenaltieswehavetoadd“long”horizontalandverticaledgestotheeditgraph.Eachsuchedgeoflengthxshouldhaveweight--x*第48页，共55页，2023年，2月20日，星期日49

/55Adding“AffinePenalty”EdgestotheEditGraphTherearemanysuchedges!Addingthemtothegraphincreasestherunningtimeofthealignmentalgorithmbyafactorofn(wherenisthenumberofvertices)SothecomplexityincreasesfromO(n2)toO(n3)第49页，共55页，2023年，2月20日，星期日50

/55Manhattanin3Layersρρσσδδδδδ第50页，共55页，2023年，2月20日，星期日51

/55AffineGapPenaltiesand3LayerManhattanGridThethreerecurr