生物信息学两两序列比对课件

大家好November22,2010

PairwisesequencealignmentJonathanPevsner,Ph.D.BioinformaticsJohnsHopkinsSchoolMed.ManyoftheimagesinthispowerpointpresentationarefromBioinformaticsandFunctionalGenomicsbyJonathanPevsner(ISBN0-471-21004-8).Copyright©2009byJohnWiley&Sons,Inc.Theseimagesandmaterialsmaynotbeusedwithoutpermissionfromthepublisher.Wewelcomeinstructorstousethesepowerpointsforeducationalpurposes,butpleaseacknowledgethesource.Thebookhasahomepageatincludinghyperlinkstothebookchapters.CopyrightnoticeAnnouncementsThemoodlequizfromlecture1isdueoneweeklater—bytodayatnoon.Afterthenthequiz“closes”andwon’tbeavailabletoyou.Thequizfromtoday’slecture(“opens”at10:30am)isdueinoneweeklateratnoon.BecauseoftheThanksgivingbreak,I’mextendingthedeadlineadaytoTuesdayNovember30(5:00pm).Outline:pairwisealignmentOverviewandexamplesDefinitions:homologs,paralogs,orthologsAssigningscorestoalignedaminoacids:Dayhoff’sPAMmatricesAlignmentalgorithms:Needleman-Wunsch,Smith-WatermanLearningobjectivesDefinehomologs,paralogs,orthologsPerformpairwisealignments(NCBIBLAST)UnderstandhowscoresareassignedtoalignedaminoacidsusingDayhoff’sPAMmatricesExplainhowtheNeedleman-WunschalgorithmperformsglobalpairwisealignmentsPairwisealignmentsinthe1950sb-corticotropin(sheep)CorticotropinA(pig)alaglygluaspaspgluaspglyalagluaspgluOxytocinVasopressinCYIQNCPLGCYFQNCPRGPage46Earlyexampleofsequencealignment:globins(1961)H.C.WatsonandJ.C.Kendrew,“ComparisonBetweentheAmino-AcidSequencesofSpermWhaleMyoglobinandofHumanHæmoglobin.”Nature190:670-672,1961.myoglobina-b-globins:•Itisusedtodecideiftwoproteins(orgenes)arerelatedstructurallyorfunctionally•ItisusedtoidentifydomainsormotifsthataresharedbetweenproteinsItisthebasisofBLASTsearching(nextweek)•ItisusedintheanalysisofgenomesPairwisesequencealignmentisthemostfundamentaloperationofbioinformaticsPage47Pairwisealignment:proteinsequencescanbemoreinformativethanDNA•proteinismoreinformative(20vs4characters);manyaminoacidssharerelatedbiophysicalproperties•codonsaredegenerate:changesinthethirdpositionoftendonotaltertheaminoacidthatisspecified•proteinsequencesofferalonger“look-back”timeDNAsequencescanbetranslatedintoprotein,andthenusedinpairwisealignmentsPage54Pairwisealignment:proteinsequencescanbemoreinformativethanDNAManytimes,DNAalignmentsareappropriate --toconfirmtheidentityofacDNA --tostudynoncodingregionsofDNA --tostudyDNApolymorphisms --example:NeanderthalvsmodernhumanDNAQuery:181catcaactacaactccaaagacacccttacacccactaggatatcaacaaacctacccac240|||||||||||||||||||||||||||||||||||||||||||||||||||||||Sbjct:189catcaactgcaaccccaaagccacccct-cacccactaggatatcaacaaacctacccac247Outline:pairwisealignmentOverviewandexamplesDefinitions:homologs,paralogs,orthologsAssigningscorestoalignedaminoacids:Dayhoff’sPAMmatricesAlignmentalgorithms:Needleman-Wunsch,Smith-WatermanPairwisealignment

Theprocessoflininguptwosequencestoachievemaximallevelsofidentity(andconservation,inthecaseofaminoacidsequences)forthepurposeofassessingthedegreeofsimilarityandthepossibilityofhomology.Definition:pairwisealignmentPage53HomologySimilarityattributedtodescentfromacommonancestor.Definition:homologyPage49Betaglobin(NP_000509)2HHBPage49myoglobin(NP_005359)2MM1Orthologs

Homologoussequencesindifferentspeciesthatarosefromacommonancestralgeneduringspeciation;mayormaynotberesponsibleforasimilarfunction.Paralogs

Homologoussequenceswithinasinglespeciesthatarosebygeneduplication.Definitions:twotypesofhomologyPage49Orthologs:membersofagene(protein)familyinvariousorganisms.Thistreeshowsglobinorthologs.Page51Youcanviewthesesequencesat(document3.1)Paralogs:membersofagene(protein)familywithinaspecies.Thistreeshowshumanglobinparalogs.Page52OrthologsandparalogsareoftenviewedinasingletreeSource:NCBIGeneralapproachtopairwisealignmentChoosetwosequencesSelectanalgorithmthatgeneratesascoreAllowgaps(insertions,deletions)ScorereflectsdegreeofsimilarityAlignmentscanbeglobalorlocalEstimateprobabilitythatthealignmentoccurredbychanceCalculationofanalignmentscoreSource:/Education/BLASTinfo/Alignment_Scores2.htmlFindBLASTfromthehomepageofNCBIandselectproteinBLAST…Page52Page52Choosealigntwoormoresequences…Enterthetwosequences(asaccessionnumbersorinthefastaformat)andclickBLAST.Optionallyselect“Algorithmparameters”andnotethematrixoption.PairwisealignmentresultofhumanbetaglobinandmyoglobinMyoglobinRefSeqQuery=HBBSubject=MBMiddlerowdisplaysidentities;+signforsimilarmatchesInformationaboutthisalignment:score,expectvalue,identities,positives,gaps…Page53Pairwisealignmentresultofhumanbetaglobinandmyoglobin:thescoreisasumofmatch,mismatch,gapcreation,andgapextensionscoresPage53Pairwisealignmentresultofhumanbetaglobinandmyoglobin:thescoreisasumofmatch,mismatch,gapcreation,andgapextensionscoresPage53VmatchingVearns+4 ThesescorescomefromTmatchingLearns-1 a“scoringmatrix”!HomologySimilarityattributedtodescentfromacommonancestor.Definitions:homologyPage50Definitions:identity,similarity,conservationIdentity

Theextenttowhichtwo(nucleotideoraminoacid)sequencesareinvariant.Page51SimilarityTheextenttowhichnucleotideorproteinsequencesarerelated.Itisbaseduponidentityplusconservation.Conservation

Changesataspecificpositionofanaminoacidor(lesscommonly,DNA)sequencethatpreservethephysico-chemicalpropertiesoftheoriginalresidue.Pairwisealignment

Theprocessoflininguptwosequencestoachievemaximallevelsofidentity(andconservation,foraminoacidsequences)forthepurposeofassessingthedegreeofsimilarityandthepossibilityofhomology.Definition:pairwisealignmentPage53MindthegapsPage55Firstgappositionscores-11 Secondgappositionscores-1 Gapcreationtendstohavealargenegativescore;Gapextensioninvolvesasmallpenalty•Positionsatwhichaletterispairedwithanullarecalledgaps.•Gapscoresaretypicallynegative.•Sinceasinglemutationaleventmaycausetheinsertionordeletionofmorethanoneresidue,thepresenceofagapisascribedmoresignificancethanthelengthofthegap.Thusthereareseparatepenaltiesforgap

creationandgapextension.•InBLAST,itisrarelynecessarytochangegapvaluesfromthedefault.Gaps1MKWVWALLLLAAWAAAERDCRVSSFRVKENFDKARFSGTWYAMAKKDPEG50RBP.||||.|...|:.||||.:|:1...MKCLLLALALTCGAQALIVT..QTMKGLDIQKVAGTWYSLAMAASD.44lactoglobulin51LFLQDNIVAEFSVDETGQMSATAKGRVR.LLNNWD..VCADMVGTFTDTE97RBP:||||::|.|.|||:|||.45ISLLDAQSAPLRV.YVEELKPTPEGDLEILLQKWENGECAQKKIIAEKTK93lactoglobulin98DPAKFKMKYWGVASFLQKGNDDHWIVDTDYDTYAVQYSC136RBP||||.|:.|||||..|94IPAVFKIDALNENKVLVLDTDYKKYLLFCMENSAEPEQSLAC135lactoglobulin137RLLNLDGTCADSYSFVFSRDPNGLPPEAQKIVRQRQ.EELCLARQYRLIV185RBP.|||:||.||||136QCLVRTPEVDDEALEKFDKALKALPMHIRLSFNPTQLEEQCHI178lactoglobulinPairwisealignmentofretinol-bindingproteinandb-lactoglobulin:Exampleofanalignmentwithinternal,terminalgaps1.MKWVWALLLLA.AWAAAERDCRVSSFRVKENFDKARFSGTWYAMAKKDP48::||||||.||.||..|:|||:.|:.||||.|||||1MLRICVALCALATCWA...QDCQVSNIQVMQNFDRSRYTGRWYAVAKKDP47.....49EGLFLQDNIVAEFSVDETGQMSATAKGRVRLLNNWDVCADMVGTFTDTED98||||||:||:|||||.|.|.||||||:||||:.||.|||||||48VGLFLLDNVVAQFSVDESGKMTATAHGRVIILNNWEMCANMFGTFEDTPD97.....99PAKFKMKYWGVASFLQKGNDDHWIVDTDYDTYAVQYSCRLLNLDGTCADS148||||||:|||||:||||||||::|||||||:||||..||||||98PAKFKMRYWGAASYLQTGNDDHWVIDTDYDNYAIHYSCREVDLDGTCLDG147.....149YSFVFSRDPNGLPPEAQKIVRQRQEELCLARQYRLIVHNGYCDGRSERNLL199|||:||||||||||||:..|:|.||:||:|:148YSFIFSRHPTGLRPEDQKIVTDKKKEICFLGKYRRVGHTGFCESS192Pairwisealignmentofretinol-bindingproteinfromhuman(top)andrainbowtrout(O.mykiss):Exampleofanalignmentwithfewgaps43210Pairwisesequencealignmentallowsustolookbackbillionsofyearsago(BYA)OriginoflifeOriginofeukaryotesinsectsFungi/animalPlant/animalEarliestfossilsEukaryote/archaeaPage56Whenyoudoapairwisealignmentofhomologoushumanandplantproteins,youarestudyingsequencesthatlastsharedacommonancestor1.5billionyearsago!flyGAKKVIISAPSAD.APM..FVCGVNLDAYKPDMKVVSNASCTTNCLAPLAhumanGAKRVIISAPSAD.APM..FVMGVNHEKYDNSLKIISNASCTTNCLAPLAplantGAKKVIISAPSAD.APM..FVVGVNEHTYQPNMDIVSNASCTTNCLAPLAbacteriumGAKKVVMTGPSKDNTPM..FVKGANFDKY.AGQDIVSNASCTTNCLAPLAyeastGAKKVVITAPSS.TAPM..FVMGVNEEKYTSDLKIVSNASCTTNCLAPLAarchaeonGADKVLISAPPKGDEPVKQLVYGVNHDEYDGE.DVVSNASCTTNSITPVAflyKVINDNFEIVEGLMTTVHATTATQKTVDGPSGKLWRDGRGAAQNIIPASThumanKVIHDNFGIVEGLMTTVHAITATQKTVDGPSGKLWRDGRGALQNIIPASTplantKVVHEEFGILEGLMTTVHATTATQKTVDGPSMKDWRGGRGASQNIIPSSTbacteriumKVINDNFGIIEGLMTTVHATTATQKTVDGPSHKDWRGGRGASQNIIPSSTyeastKVINDAFGIEEGLMTTVHSLTATQKTVDGPSHKDWRGGRTASGNIIPSSTarchaeonKVLDEEFGINAGQLTTVHAYTGSQNLMDGPNGKP.RRRRAAAENIIPTSTflyGAAKAVGKVIPALNGKLTGMAFRVPTPNVSVVDLTVRLGKGASYDEIKAKhumanGAAKAVGKVIPELNGKLTGMAFRVPTANVSVVDLTCRLEKPAKYDDIKKVplantGAAKAVGKVLPELNGKLTGMAFRVPTSNVSVVDLTCRLEKGASYEDVKAAbacteriumGAAKAVGKVLPELNGKLTGMAFRVPTPNVSVVDLTVRLEKAATYEQIKAAyeastGAAKAVGKVLPELQGKLTGMAFRVPTVDVSVVDLTVKLNKETTYDEIKKVarchaeonGAAQAATEVLPELEGKLDGMAIRVPVPNGSITEFVVDLDDDVTESDVNAAMultiplesequencealignmentofglyceraldehyde3-phosphatedehydrogenases:exampleofextremelyhighconservationPage57Outline:pairwisealignmentOverviewandexamplesDefinitions:homologs,paralogs,orthologsAssigningscorestoalignedaminoacids:Dayhoff’sPAMmatricesAlignmentalgorithms:Needleman-Wunsch,Smith-WatermanPage93EmileZuckerkandlandLinusPauling(1965)consideredsubstitutionfrequenciesin18globins(myoglobinsandhemoglobinsfromhumantolamprey).Black:identityGray:veryconservativesubstitutions(>40%occurrence)White:fairlyconservativesubstitutions(>21%occurrence)Red:nosubstitutionsobservedlysfoundat58%ofargsitesPage93Wherewe’reheading:toaPAM250logoddsscoringmatrixthatassignsscoresandisforgivingofmismatches…(suchas+17forWtoW or-5forWtoT)Page69Page69…andtoawholeseriesofscoringmatricessuchasPAM10thatarestrictanddonottoleratemismatches(suchas+13forWtoW or-19forWtoT)Dayhoff’s34proteinsuperfamiliesProtein

PAMsper100millionyearsIgkappachain 37Kappacasein 33luteinizinghormoneb 30lactalbumin 27complementcomponent3 27epidermalgrowthfactor 26proopiomelanocortin 21pancreaticribonuclease 21haptoglobinalpha 20serumalbumin 19phospholipaseA2,groupIB 19prolactin 17carbonicanhydraseC 16Hemoglobina 12Hemoglobinb 12Page59Dayhoff’s34proteinsuperfamiliesProtein

PAMsper100millionyearsIgkappachain 37Kappacasein 33luteinizinghormoneb 30lactalbumin 27complementcomponent3 27epidermalgrowthfactor 26proopiomelanocortin 21pancreaticribonuclease 21haptoglobinalpha 20serumalbumin 19phospholipaseA2,groupIB 19prolactin 17carbonicanhydraseC 16Hemoglobina 12Hemoglobinb 12human(NP_005203)versusmouse(NP_031812)Dayhoff’s34proteinsuperfamiliesProtein

PAMsper100millionyearsapolipoproteinA-II 10lysozyme 9.8gastrin 9.8myoglobin 8.9nervegrowthfactor 8.5myelinbasicprotein 7.4thyroidstimulatinghormoneb 7.4parathyroidhormone 7.3parvalbumin 7.0trypsin 5.9insulin 4.4calcitonin 4.3argininevasopressin 3.6adenylatekinase1 3.2Page59Dayhoff’s34proteinsuperfamiliesProtein

PAMsper100millionyearstriosephosphateisomerase1 2.8vasoactiveintestinalpeptide 2.6glyceraldehydephosph.dehydrogease 2.2cytochromec 2.2collagen 1.7troponinC,skeletalmuscle 1.5alphacrystallinBchain 1.5glucagon 1.2glutamatedehydrogenase 0.9histoneH2B,memberQ 0.9ubiquitin 0Page59Pairwisealignmentofhuman(NP_005203)versusmouse(NP_031812)ubiquitinDayhoff’snumbersof“acceptedpointmutations”:whataminoacidsubstitutionsoccurinproteins?Page61Dayhoff(1978)p.346.flyGAKKVIISAPSAD.APM..FVCGVNLDAYKPDMKVVSNASCTTNCLAPLAhumanGAKRVIISAPSAD.APM..FVMGVNHEKYDNSLKIISNASCTTNCLAPLAplantGAKKVIISAPSAD.APM..FVVGVNEHTYQPNMDIVSNASCTTNCLAPLAbacteriumGAKKVVMTGPSKDNTPM..FVKGANFDKY.AGQDIVSNASCTTNCLAPLAyeastGAKKVVITAPSS.TAPM..FVMGVNEEKYTSDLKIVSNASCTTNCLAPLAarchaeonGADKVLISAPPKGDEPVKQLVYGVNHDEYDGE.DVVSNASCTTNSITPVAflyKVINDNFEIVEGLMTTVHATTATQKTVDGPSGKLWRDGRGAAQNIIPASThumanKVIHDNFGIVEGLMTTVHAITATQKTVDGPSGKLWRDGRGALQNIIPASTplantKVVHEEFGILEGLMTTVHATTATQKTVDGPSMKDWRGGRGASQNIIPSSTbacteriumKVINDNFGIIEGLMTTVHATTATQKTVDGPSHKDWRGGRGASQNIIPSSTyeastKVINDAFGIEEGLMTTVHSLTATQKTVDGPSHKDWRGGRTASGNIIPSSTarchaeonKVLDEEFGINAGQLTTVHAYTGSQNLMDGPNGKP.RRRRAAAENIIPTSTflyGAAKAVGKVIPALNGKLTGMAFRVPTPNVSVVDLTVRLGKGASYDEIKAKhumanGAAKAVGKVIPELNGKLTGMAFRVPTANVSVVDLTCRLEKPAKYDDIKKVplantGAAKAVGKVLPELNGKLTGMAFRVPTSNVSVVDLTCRLEKGASYEDVKAAbacteriumGAAKAVGKVLPELNGKLTGMAFRVPTPNVSVVDLTVRLEKAATYEQIKAAyeastGAAKAVGKVLPELQGKLTGMAFRVPTVDVSVVDLTVKLNKETTYDEIKKVarchaeonGAAQAATEVLPELEGKLDGMAIRVPVPNGSITEFVVDLDDDVTESDVNAAMultiplesequencealignmentofglyceraldehyde3-phosphatedehydrogenases:columnsofresiduesmayhavehighorlowconservationPage57TherelativemutabilityofaminoacidsAsn 134 His 66Ser 120 Arg 65Asp 106 Lys 56Glu 102 Pro 56Ala 100 Gly 49Thr 97 Tyr 41Ile 96 Phe 41Met 94 Leu 40Gln 93 Cys 20Val 74 Trp 18Page63NormalizedfrequenciesofaminoacidsGly 8.9% Arg 4.1%Ala 8.7% Asn 4.0%Leu 8.5% Phe 4.0%Lys 8.1% Gln 3.8%Ser 7.0% Ile 3.7%Val 6.5% His 3.4%Thr 5.8% Cys 3.3%Pro 5.1% Tyr 3.0%Glu 5.0% Met 1.5%Asp 4.7% Trp 1.0%blue=6codons;red=1codonThesefrequenciesfisumto1Page63Dayhoff’snumbersof“acceptedpointmutations”:whataminoacidsubstitutionsoccurinproteins?Page61Dayhoff’sPAM1mutationprobabilitymatrixOriginalaminoacidPage66Dayhoff’sPAM1mutationprobabilitymatrixEachelementofthematrixshowstheprobabilitythatanoriginalaminoacid(top)willbereplacedbyanotheraminoacid(side)Asubstitutionmatrixcontainsvaluesproportionaltotheprobabilitythataminoacidimutatesintoaminoacidjforallpairsofaminoacids.Substitutionmatricesareconstructedbyassemblingalargeanddiversesampleofverifiedpairwisealignments(ormultiplesequencealignments)ofaminoacids.

Substitutionmatricesshouldreflectthetrueprobabilitiesofmutationsoccurringthroughaperiodofevolution.ThetwomajortypesofsubstitutionmatricesarePAMandBLOSUM.SubstitutionMatrixPAMmatricesarebasedonglobalalignmentsofcloselyrelatedproteins.ThePAM1isthematrixcalculatedfromcomparisonsofsequenceswithnomorethan1%divergence.AtanevolutionaryintervalofPAM1,onechangehasoccurredoveralengthof100aminoacids.OtherPAMmatricesareextrapolatedfromPAM1.ForPAM250,250changeshaveoccurredfortwoproteinsoveralengthof100aminoacids.AllthePAMdatacomefromcloselyrelatedproteins(>85%aminoacididentity).PAMmatrices:Point-acceptedmutationsPage63Dayhoff’sPAM1mutationprobabilitymatrixPage66Dayhoff’sPAM0mutationprobabilitymatrix:therulesforextremelyslowlyevolvingproteinsTop:originalaminoacidSide:replacementaminoacidPage68Dayhoff’sPAM2000mutationprobabilitymatrix:therulesforverydistantlyrelatedproteinsPAMAAlaRArgNAsnDAspCCysQGlnEGluGGlyA8.7%8.7%8.7%8.7%8.7%8.7%8.7%8.7%R4.1%4.1%4.1%4.1%4.1%4.1%4.1%4.1%N4.0%4.0%4.0%4.0%4.0%4.0%4.0%4.0%D4.7%4.7%4.7%4.7%4.7%4.7%4.7%4.7%C3.3%3.3%3.3%3.3%3.3%3.3%3.3%3.3%Q3.8%3.8%3.8%3.8%3.8%3.8%3.8%3.8%E5.0%5.0%5.0%5.0%5.0%5.0%5.0%5.0%G8.9%8.9%8.9%8.9%8.9%8.9%8.9%8.9%Top:originalaminoacidSide:replacementaminoacidPage68PAM250mutationprobabilitymatrixTop:originalaminoacidSide:replacementaminoacidPage68PAM250logoddsscoringmatrixPage69Whydowegofromamutationprobabilitymatrixtoalogoddsmatrix?Wewantascoringmatrixsothatwhenwedoapairwisealignment(oraBLASTsearch)weknowwhatscoretoassigntotwoalignedaminoacidresidues.Logarithmsareeasiertouseforascoringsystem.Theyallowustosumthescoresofalignedresidues(ratherthanhavingtomultiplythem).Page69Howdowegofromamutationprobabilitymatrixtoalogoddsmatrix?Thecellsinalogoddsmatrixconsistofan“oddsratio”:

theprobabilitythatanalignmentisauthentic theprobabilitythatthealignmentwasrandomThescoreSforanalignmentofresiduesa,bisgivenby:S(a,b)=10log10(Mab/pb)Asanexample,fortryptophan,S(trp,trp)=10log10(0.55/0.010)=17.4Page69Whatdothenumbersmeaninalogoddsmatrix?Ascoreof+2indicatesthattheaminoacidreplacementoccurs1.6timesasfrequentlyasexpectedbychance.Ascoreof0isneutral.Ascoreof–10indicatesthatthecorrespondenceoftwoaminoacidsinanalignmentthataccuratelyrepresentshomology(evolutionarydescent)isonetenthasfrequentasthechancealignmentoftheseaminoacids.Page58RatversusmouseglobinRatversusbacterialglobinMoreconservedLessconservedBLOSUMmatricesarebasedonlocalalignments.BLOSUMstandsforblockssubstitutionmatrix.BLOSUM62isamatrixcalculatedfromcomparisonsofsequenceswithnolessthan62%divergence.BLOSUMMatricesPage70BLOSUMMatrices1006230PercentaminoacididentityBLOSUM62collapseBLOSUMMatrices1006230PercentaminoacididentityBLOSUM621006230BLOSUM301006230BLOSUM80collapsecollapsecollapseBlosum62scoringmatrixPage73PercentidentityEvolutionarydistanceinPAMsTworandomlydivergingproteinsequenceschangeinanegativelyexponentialfashion“twilightzone”Page74PercentidentityDifferencesper100residuesAtPAM1,twoproteinsare99%identicalAtPAM10.7,thereare10differencesper100residuesAtPAM80,thereare50differencesper100residuesAtPAM250,thereare80differencesper100residues“twilightzone”Page75PAM:“Acceptedpointmutation”Twoproteinswith50%identitymayhave80changesper100residues.(Why?Becauseanyresiduecanbesubjecttobackmutations.)Proteinswith20%to25%identityareinthe“twilightzone”andmaybestatisticallysignificantlyrelated.PAMor“acceptedpointmutation”referstothe“hits”ormatchesbetweentwosequences(Dayhoff&Eck,1968)Page75Outline:pairwisealignmentOverviewandexamplesDefinitions:homologs,paralogs,orthologsAssigningscorestoalignedaminoacids:Dayhoff’sPAMmatricesAlignmentalgorithms:Needleman-Wunsch,Smith-WatermanWewillfirstconsidertheglobalalignmentalgorithmofNeedlemanandWunsch(1970).WewillthenexplorethelocalalignmentalgorithmofSmithandWaterman(1981).Finally,wewillconsiderBLAST,aheuristicversionofSmith-Waterman.WewillcoverBLASTindetailonMonday.Twokindsofsequencealignment:globalandlocalPage76•Twosequencescanbecomparedinamatrixalongx-andy-axes.•Iftheyareidentical,apathalongadiagonalcanbedrawn•Findtheoptimalsubpaths,andaddthemuptoachievethebestscore.Thisinvolves --addinggapswhenneeded --allowingforconservativesubstitutions --choosingascoringsystem(simpleorcomplicated)N-Wisguaranteedtofindoptimalalignment(s)GlobalalignmentwiththealgorithmofNeedlemanandWunsch(1970)Page76[1]setupamatrix[2]scorethematrix[3]identifytheoptimalalignment(s)ThreestepstoglobalalignmentwiththeNeedleman-WunschalgorithmPage76 [1]identity(stayalongadiagonal) [2]mismatch(stayalongadiagonal) [3]gapinonesequence(movevertically!) [4]gapintheothersequence(movehorizontally!)Fourpossibleoutcomesinaligningtwosequences12Page77Page77StartNeedleman-WunschwithanidentitymatrixPage77StartNeedleman-WunschwithanidentitymatrixPage77Fillinthematrixusing“dynamicprogramming”Page78Fillinthematrixusing“dynamicprogramming”Page78Fillinthematrixusing“dynamicprogramming”Page78Fillinthematrixusing“dynamicprogramming”Page78Fillinthematrixusing“dynamicprogramming”Page78Fillinthematrixusing“dynamicprogramming”Page78Fillinthematrixusing“dynamicprogramming”Page78Tracebacktofindtheoptimal(best)pairwisealignmentPage79N-Wisguaranteedtofindoptimalalignments,althoughthealgorithmdoesnotsearchallpossiblealignments.Itisanexampleofadynamicprogrammingalgorithm:anoptimalpath(alignment)isidentifiedbyincrementallyextendingoptimalsubpaths.Thus,aseriesofdecisionsismadeateachstepofthealignmenttofindthepairofresidueswiththebestscore.Needleman-Wunsch:dynamicprogrammingPage80TryusingneedletoimplementaNeedleman-Wunschglobalalignmentalgorithmtofindtheoptimumalignment(includinggaps):http://www.ebi.ac.uk/emboss/align/Page81Queries:betaglobin(NP_000509)alphaglobin(NP_000549)Globalalignment(Needleman-Wunsch)extendsfromoneendofeachsequencetotheother.Localalignmentfindsoptimallymatchingregionswithintwosequences(“subsequences”).LocalalignmentisalmostalwaysusedfordatabasesearchessuchasBLAST.Itisusefultofinddomains(orlimitedregionsofhomology)withinsequences.SmithandWaterman(1981)solvedtheproblemofperformingoptimallocalsequencealignment.Othermethods(BLAST,FASTA)aref