動態(tài)規(guī)劃法雙序列比對第一頁，共五十五頁，2022年，8月28日2

/55習(xí)題4，求兩條序列的最長共同子序列?！咀鳂I(yè)】v=TACGGGTATw=GGACGTACG第二頁，共五十五頁，2022年，8月28日3

/550123456789000000000001020304050607080905GGACGTACGTACGGGTAT第三頁，共五十五頁，2022年，8月28日4SequenceAlignment第四頁，共五十五頁，2022年，8月28日5

/55OutlineGlobalAlignmentScoringMatricesLocalAlignmentAlignmentwithAffineGapPenalties第五頁，共五十五頁，2022年，8月28日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第六頁，共五十五頁，2022年，8月28日7

/55SimpleScoringWhenmismatchesarepenalizedby–μ,indelsarepenalizedby–σ,andmatchesarerewardedwith+1,theresultingscoreis:#matches–μ(#mismatches)–σ(#indels)第七頁，共五十五頁，2022年，8月28日8

/55TheGlobalAlignmentProblemFindthebestalignmentbetweentwostringsunderagivenscoringschemaInput:StringsvandwandascoringschemaOutput:Alignmentofmaximumscorem:mismatchpenaltyσ:indelpenalty第八頁，共五十五頁，2022年，8月28日9

/55ScoringMatricesTogeneralizescoring,considera(4+1)x(4+1)scoringmatrixδ.Inthecaseofanaminoacidsequencealignment,thescoringmatrixwouldbea(20+1)x(20+1)size.Theadditionof1istoincludethescoreforcomparisonofagapcharacter“-”.Thiswillsimplifythealgorithmasfollows:第九頁，共五十五頁，2022年，8月28日10

/55TheBlosum62ScoringMatrix第十頁，共五十五頁，2022年，8月28日11

/55MeasuringSimilarityMeasuringtheextentofsimilaritybetweentwosequencesBasedonpercentsequenceidentityBasedonconservation第十一頁，共五十五頁，2022年，8月28日12

/55PercentSequenceIdentityTheextenttowhichtwonucleotideoraminoacidsequencesareinvariantACCTGAG–AGACGTG–GCAG70%identicalmismatchindel第十二頁，共五十五頁，2022年，8月28日13

/55MakingaScoringMatrixScoringmatricesarecreatedbasedonbiologicalevidence.Alignmentscanbethoughtofastwosequencesthatdifferduetomutations.Someofthesemutationshavelittleeffectontheprotein’sfunction,thereforesomepenalties,δ(vi,wj),willbelessharshthanothers.第十三頁，共五十五頁，2022年，8月28日14

/55ScoringMatrix:ExampleAKRANRKAAANK-1+(-1)+(-2)+5+7+3=11ARNKA5-2-1-1R-7-13N--70K---6NoticethatalthoughRandKaredifferentaminoacids,theyhaveapositivescore.Why?Theyarebothpositivelychargedaminoacidswillnotgreatlychangefunctionofprotein.第十四頁，共五十五頁，2022年，8月28日15

/55ConservationAminoacidchangesthattendtopreservethephysico-chemicalpropertiesoftheoriginalresiduePolartopolaraspartateglutamateNonpolartononpolaralaninevalineSimilarlybehavingresiduesleucinetoisoleucine第十五頁，共五十五頁，2022年，8月28日16

/55ScoringmatricesAminoacidsubstitutionmatricesPAMBLOSUMDNAsubstitutionmatricesDNAislessconservedthanproteinsequencesLesseffectivetocomparecodingregionsatnucleotidelevel第十六頁，共五十五頁，2022年，8月28日17

/55PAMPointAcceptedMutation(Dayhoffetal.)1PAM=PAM1=1%averagechangeofallaminoacidpositionsAfter100PAMsofevolution,noteveryresiduewillhavechangedsomeresiduesmayhavemutatedseveraltimessomeresiduesmayhavereturnedtotheiroriginalstatesomeresiduesmaynotchangedatall第十七頁，共五十五頁，2022年，8月28日18

/55PAMXPAMx=PAM1xPAM250=PAM1250PAM250isawidelyusedscoringmatrix:

AlaArgAsnAspCysGlnGluGlyHisIleLeuLys...ARNDCQEGHILK...AlaA13699589126867...ArgR3174325326329AsnN446725646325AspD54811171056325CysC2111521122211GlnQ3556110737235...TrpW020000001010TyrY112131113221ValV74444444541510第十八頁，共五十五頁，2022年，8月28日19

/55BLOSUMBlocksSubstitutionMatrixScoresderivedfromobservationsofthefrequenciesofsubstitutionsinblocksoflocalalignmentsinrelatedproteinsMatrixnameindicatesevolutionarydistanceBLOSUM62wascreatedusingsequencessharingnomorethan62%identity第十九頁，共五十五頁，2022年，8月28日20

/55TheBlosum62ScoringMatrixBLOSUM62第二十頁，共五十五頁，2022年，8月28日21

/55BLOSUM90PAM30低趨異度小鼠和大鼠RBPBLOSUM45PAM240高趨異度小鼠和細菌的lipocalinBLOSUM80PAM120BLOSUM62PAM180相似度越低的序列，在比對的時候，采用PAM矩陣時，后面的數(shù)字越大，采用BLOSUM矩陣時，后面的數(shù)字越小。第二十一頁，共五十五頁，2022年，8月28日22

/55Localvs.GlobalAlignmentTheGlobalAlignmentProblemtriestofindthelongestpathbetweenvertices(0,0)and(n,m)intheeditgraph.TheLocalAlignmentProblemtriestofindthelongestpathamongpathsbetweenarbitraryvertices(i,j)and(i’,j’)intheeditgraph.第二十二頁，共五十五頁，2022年，8月28日23

/55Localvs.GlobalAlignmentTheGlobalAlignmentProblemtriestofindthelongestpathbetweenvertices(0,0)and(n,m)intheeditgraph.TheLocalAlignmentProblemtriestofindthelongestpathamongpathsbetweenarbitraryvertices(i,j)and(i’,j’)intheeditgraph.Intheeditgraphwithnegatively-scorededges,LocalAlignmetmayscorehigherthanGlobalAlignment第二十三頁，共五十五頁，2022年，8月28日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第二十四頁，共五十五頁，2022年，8月28日25

/55LocalAlignment:ExampleGlobalalignmentLocalalignmentComputea“mini”GlobalAlignmenttogetLocal第二十五頁，共五十五頁，2022年，8月28日26

/55LocalAlignments:Why?Twogenesindifferentspeciesmaybesimilarovershortconservedregionsanddissimilaroverremainingregions.Example:Homeoboxgeneshaveashortregioncalledthehomeodomainthatishighlyconservedbetweenspecies.AglobalalignmentwouldnotfindthehomeodomainbecauseitwouldtrytoaligntheENTIREsequence第二十六頁，共五十五頁，2022年，8月28日27

/55TheLocalAlignmentProblemGoal:FindthebestlocalalignmentbetweentwostringsInput:Stringsv,wandscoringmatrixδOutput:Alignmentofsubstringsofvandwwhosealignmentscoreismaximumamongallpossiblealignmentofallpossiblesubstrings第二十七頁，共五十五頁，2022年，8月28日28

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

-Foreachsuchvertexcomputingalignmentsfrom(i,j)to(i’,j’)takesO(n2)time.Thiscanberemediedbygivingfreerides第二十八頁，共五十五頁，2022年，8月28日29

/55LocalAlignment:ExampleGlobalalignmentLocalalignmentComputea“mini”GlobalAlignmenttogetLocal第二十九頁，共五十五頁，2022年，8月28日30

/55LocalAlignment:Example第三十頁，共五十五頁，2022年，8月28日31

/55LocalAlignment:Example第三十一頁，共五十五頁，2022年，8月28日32

/55LocalAlignment:Example第三十二頁，共五十五頁，2022年，8月28日33

/55LocalAlignment:Example第三十三頁，共五十五頁，2022年，8月28日34

/55LocalAlignment:Example第三十四頁，共五十五頁，2022年，8月28日35

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

-Foreachsuchvertexcomputingalignmentsfrom(i,j)to(i’,j’)takesO(n2)time.Thiscanberemediedbygivingfreerides第三十五頁，共五十五頁，2022年，8月28日36

/55LocalAlignment:FreeRidesVertex(0,0)Thedashededgesrepresentthefreeridesfrom(0,0)toeveryothernode.Yeah,afreeride!第三十六頁，共五十五頁，2022年，8月28日37

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

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

(vi,-)

si,j-1+δ

(-,wj){NoticethereisonlythischangefromtheoriginalrecurrenceofaGlobalAlignment第三十七頁，共五十五頁，2022年，8月28日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第三十八頁，共五十五頁，2022年，8月28日39

/55

NP_006735NP_000945第三十九頁，共五十五頁，2022年，8月28日40

/55第四十頁，共五十五頁，2022年，8月28日41

/55習(xí)題考慮序列v=TACGGGTAT和w=GGACGTACG。假設(shè)匹配獎勵+1，錯配和插缺罰分均為-1.【作業(yè)】填寫序列v和w之間的全局聯(lián)配的動態(tài)規(guī)劃表（編輯圖或相似度矩陣）。在各單元畫出箭頭以存儲返回信息。全局最優(yōu)聯(lián)配的得分是多少？這個得分對應(yīng)的聯(lián)配又是什么？填寫序列v和w之間的局部聯(lián)配的動態(tài)規(guī)劃表。在各單元畫出箭頭以存儲返回信息。在這種情形下，局部最優(yōu)聯(lián)配的得分是多少？這個得分對應(yīng)的聯(lián)配又是什么？第四十一頁，共五十五頁，2022年，8月28日42

/55-012345678900-1-2-3-4-5-6-7-8-91-12-23-34-45-56-67-78-899GGACGTACGTACGGGTAT全局比對第四十二頁，共五十五頁，2022年，8月28日43

/55局部比對-012345678900000000000102030405060708090GGACGTACGTACGGGTAT第四十三頁，共五十五頁，2022年，8月28日44

/55ScoringIndels:NaiveApproachAfixedpenaltyσ

isgiventoeveryindel:-σfor1indel,-2σfor2consecutiveindels-3σfor3consecutiveindels,etc.Canbetooseverepenaltyforaseriesof100consecutiveindels第四十四頁，共五十五頁，2022年，8月28日45

/55AffineGapPenaltiesInnature,aseriesofkindelsoftencomeasasingleeventratherthanaseriesofksinglenucleotideevents:ATA__GCATATTGCATAG_GCAT_GTGCNormalscoringwouldgivethesamescoreforbothalignmentsThisismorelikely.Thisislesslikely.第四十五頁，共五十五頁，2022年，8月28日46

/55AccountingforGapsGaps-contiguoussequenceofspacesinoneoftherowsScoreforagapoflengthxis:-(ρ+

σx)whereρ>0isthepenaltyforintroducingagap:gapopeningpenalty

ρwillbelargerelativetoσ:

gapextensionpenaltybecauseyoudonotwanttoaddtoomuchofapenaltyforextendingthegap.第四十六頁，共五十五頁，2022年，8月28日47

/55AffineGapPenaltiesGappenalties:-ρ-σwhenthereis1indel-ρ-2σwhenthereare2indels-ρ-3σwhenthereare3indels,etc.-ρ-x·σ(-gapopening-xgapextensions)Somehowreducedpenalties(ascomparedtona?vescoring)aregiventorunsofhorizontalandverticaledges第四十七頁，共五十五頁，2022年，8月28日48

/55AffineGapPenaltiesandEditGraphToreflectaffinegappenaltieswehavetoadd“l(fā)ong”horizontalandverticaledgestotheeditgraph.Eachsuchedgeoflengthxshouldhaveweight--x*第四十八頁，共五十五頁，2022年，8月28日49

/55Adding“AffinePenalty”EdgestotheEditGraphTherearemanysuchedges!Addingthemtothegraphincreasestherunningtimeofthealignmentalgorithmbyafactorofn(wherenisthenumberofvertices)SothecomplexityincreasesfromO(n2)toO(n3)第四十九頁，共五十五頁，2022年，8月28日50

/55Manhattanin3Layersρρσσδδδδδ第五十頁，共五十五頁，2022年，8月28日51

/55AffineGapPenaltiesand3LayerManhattanGridThethreerecurrences