SequenceAlignment-Lirq.ppt

SequenceAlignment 李瑞强lirq AspectsofBioinformaticsAnalysis Genomeassembly genomestructure repeat genedistribution Comparativegenomics synteny rearrangment duplication Genefinding motifdetection Pairwisealignment multi alignment genefamily phylogeny Microarraydesign signalrecognition clustering quantitation Molecularevolution Ka Ks Protein2D 3Dstructure homology domain functionalprediction deleteriousmutation Massspectrometry peptidesearch quantitation modification interaction SNP heterozygosis haplotype recombination association Softwarepipeline databaseconstruction Sequencealignment thefoundationofinformaticsanalysis DynamicprogrammingSubstitutionmatrix gappenaltiesGlobalandlocalalignmentGappedblastandPSI blastMulti alignment DPinequationform Alignsequencexandy FistheDPmatrix sisthesubstitutionmatrix disthelineargappenalty DPinequationform Asimpleexample FindtheoptimalalignmentofAAGandAGC Useagappenaltyofd 5 Asimpleexample FindtheoptimalalignmentofAAGandAGC Useagappenaltyofd 5 Asimpleexample FindtheoptimalalignmentofAAGandAGC Useagappenaltyofd 5 Asimpleexample FindtheoptimalalignmentofAAGandAGC Useagappenaltyofd 5 Traceback Startfromthelowerrightcornerandtracebacktotheupperleft Eacharrowintroducesonecharacterattheendofeachalignedsequence Ahorizontalmoveputsagapintheleftsequence Averticalmoveputsagapinthetopsequence Adiagonalmoveusesonecharacterfromeachsequence Startfromthelowerrightcornerandtracebacktotheupperleft Eacharrowintroducesonecharacterattheendofeachalignedsequence Ahorizontalmoveputsagapintheleftsequence Averticalmoveputsagapinthetopsequence Adiagonalmoveusesonecharacterfromeachsequence Asimpleexample FindtheoptimalalignmentofAAGandAGC Useagappenaltyofd 5 Asimpleexample FindtheoptimalalignmentofAAGandAGC Useagappenaltyofd 5 AAG AAG AGCA GC 1 2 Complexity Space O mn Time O mn FillingthematrixO mn BacktraceO m n Otherscoringschemes NeedlemanandWunsch 1foridenticalaminoacid 0otherwiseDayhoffPAMscoringmatrix variationsincludeBLOSUMmatrices HenikoffandHenikoff1992 Proc Nat Acad Sci 89 10915 10919 DifferentGapCostFunction BLOSUM62 Scoringmatrixforproteinsequences Aminoacids chemicalproperties Also Residualcolours aproposalforaminochromography Taylor Prot Eng 10 743 7461997 Gappenalties Iflowenough canalignanythingPenaltiesassociatedwithascoringmatrixTwocommonvarieties GapopeningcostsameasgapextensioncostOpeningandextensioncostsdifferent extensionmuchsmallerthanopening ATCGATTACCCAAGGGACGAA C A TAC CAA GG A A Anexampleofpeptidepairwisealignment Seq1 HEAGAWGHEESeq2 PAWHEAE HEAGAWGHE E P A W HEAE HEAGAWGHE E P AW HEAE Whichoneisbetter Alignment 1 Alignment 2 Traceback TracearrowsbackfromthelowerrighttotopleftDiagonal bothUp uppergapLeft lowergap HEAGAWGHE E P AW HEAE TypesofAlignment GlobalfindbestalignmentofentirelengthsNeedleman WunschalgorithmLocalhighestscoringregionofsimilaritynatureofsequenceevolutionmakesthisvastlymoreusefulfordatabasesearchingSmith Watermanalgorithmblast fastaetc useheuristicstospeedsearch LocalAlignment Smith Waterman 1981 Anotherdynamicprogrammingsolution Example Traceback Startathighestscoreandtracebacktofirst0 HEAGAWGHEE PAW HEAE Summary SimilartoglobalalignmentalgorithmForthistowork expectedmatchwithrandomsequencemusthavenegativescore BehaviorislikeglobalalignmentotherwiseSimilarextensionsforrepeatedandoverlapmatching BLASTAlgorithm ABCDEFGHIJKLMNCDDOPQACDERSHAGGPIFYLMLST Extensioncriteria one hit two hit ABCDEFGHIJKLMNCDDOPQACDERSHAGGPIFYLMLST SHSP hit BlastWordSize Query 4tcttctccaatgtgatgatggagttgaatgaacttaggactccactccaaggttgacttg63 Sbjct 2tctactctaatgtgatgctgggattgaattttcctaggactccgtttcaaggttaattcg61Query 64aaaggtgtgtagaagat80 Sbjct 62aaagtcttgtggaagat78 Minimumwordsizeof9neededtodetectsimilarity defaultis11 Forproteinswordsizeis3 matchneednotbeexact lessofanissue ABalancebetweenSpeedandSensitivity PSIBLAST Position SpecificIteratedBLASTIncorporatespositionspecificmatrices profiles OftenmuchbetteratdetectingweaksimilaritiesBeforePSIBLASTthesametechniqueswereused butalargedegreeofexpertiseandhumaninterventionwasrequired Itcandoaniterativesearchinwhichsequencesfoundinoneroundofsearchingareusedtobuildascoremodelforthenextroundofsearching Inthisusage theprogramiscalledPosition SpecificIteratedBLAST orPSI BLAST Flowchart ScoreMatrixArchitecture ProfilesverysimilartoscoringmatrixProteinornucleotidealignstoprofilepositionNewprofilecreatedwitheveryiterationProfilescreatedinturniusedinturni 1Gapcostsmaybeposition specificwithprofiles HowpositionspecificproteinscorematricesdrawtheirpowerImprovedestimationoftheprobabilitieswithwhichaminoacidsoccuratvariouspatternpositionsRelativelyprecisedefinitionoftheboundariesofimportantmotifsEverymatrixconstructedhasalengthexactlythesameastheoriginalquerysequence MultipleAlignmentConstruction SequenceWeights AlldatabasesequenceswhosealignedE valueisbelowaspecificthresholdareaddedtothequeryAnyrow orcolumn whichis 98 identicaltoapreviouslyaddedalignmentiskeptoutoftheprofileAllowsforbettersearchingonlateriterationsPoorrestrictionscouldleadtolargescaleprofilesequenceinsertionSequencesaregivendifferentweightsdependingonevolutionaryimportance MultipleSequenceAlignmentandtheIterations Position specificscorematrix PSIBLASTOverview Startoffwithqueryandinitialscorematrix BLOSUM62 HomologsarefoundusingBLAST alignDBtoquery E ValueisusedascriteriaforsequenceinsertionintoprofileAprofile p1 isconstructedfromthepassingsequencesandscorematrixOnceagainsearchforhomologsusingBLAST alignDBtoprofile OnceagainuseE ValueascriteriaforinsertionintoprofileAprofile p2 isconstructedfromtheapprovedsequencesandscorematirx Multi Alignment MultipleAlignment multipledimensions ProgressiveAlignmentProfileProgressiveAlignment ClustalW GeneralizingtheNotionofPairwiseAlignment Upuntilnowwehaveonlytriedtoaligntwosequencestooneanother Whataboutmorethantwo Werepresentedalignmentof2sequencesasa2 rowmatrixInasimilarway werepresentalignmentof3sequencesasa3 rowmatrixAT GCG A CGT AATCAC AScore moreconservedcolumns betteralignment AligningThreeSequences SamestrategyasaligningtwosequencesUsea3 D ManhattanCube witheachaxisrepresentingasequencetoalignForglobalalignments gofromsourcetosink source sink 2 Dvs3 DAlignmentGrid V W 2 Deditgraph 3 D Architectureof3 DAlignmentGrid In3 D 7edgesineachunitcube In2 D 3edgesineachunitsquare ACellof3 DAlignmentGrid i 1 j 1 k 1 i j 1 k 1 i j 1 k i 1 j 1 k i 1 j k i j k i 1 j k 1 i j k 1 MultipleAlignment DynamicProgramming Si j k max x y z isanentryinthe3 Dscoringmatrix whichisalsoofenhanceddimension squarediagonal noindels facediagonal oneindel edgediagonal twoindels AlignmentPaths Alignthefollowing3sequences ATGC AATC ATGC Resultingpath x y z 0 0 0 1 1 0 1 2 1 2 3 2 3 3 3 4 4 4 xcoordinate ycoordinate zcoordinate MultipleAlignment RunningTime For3sequencesoflengthn theruntimeis7n3 O n3 Forksequences buildak dimensionalManhattan withruntime 2k 1 nk O 2knk Conclusion dynamicprogrammingapproachforalignmentbetweentwosequencesiseasilyextendedtoksequencesbutitisimpracticalduetoexponentialrunningtime CombiningOptimalPairwiseAlignmentsintoMultipleAlignment Cancombinepairwiseintomultiplealignment Cannotcombinepairwiseintomultiplealignment MultipleAlignment GreedyApproach Choosemostsimilarpairofstrings combineintoaconsensus therebyreducingksequencestoaofk 1sequences RepeatThisisaheuristicgreedymethod u1 ACGTACGTACGT u2 TTAATTAATTAA u3 ACTACTACTACT uk CCGGCCGGCCGG u1 AC TAC TAC T u2 TTAATTAATTAA uk CCGGCCGGCCGG k k 1 GreedyApproach Example Considerthese4sequences s1GATTCAs2GTCTGAs3GATATTs4GTCAGC GreedyApproach Example cont d Thereare 6possiblealignments s2GTCTGAs4GTCAGC score 2 s1GAT TCAs2G TCTGA score 1 s1GAT TCAs3GATAT T score 1 s1GATTCA s4G T CAGC score 0 s2G TCTGAs3GATAT T score 1 s3GAT ATTs4G TCAGC score 1 GreedyApproach Example cont d s2ands4areclosest combine s2GTCTGAs4GTCAGC s2 4GTCTGA consensus s1GATTCAs3GATATTs2 4GTCTGA newsetbecomes GreedyApproach Example cont d s1GATTCAs3GATATTs2 4GTCTGA setis s1GAT TCAs3GATAT T score 1 s1GATTC As2 4G T CTGA score 0 s3GATATT s2 4G TCTGA score 1 scoresare Takebestpairandformanotherconsensus s1 3 GATATT arbitrarilybreakties GreedyApproach Example cont d newsetis s1 3GATATTs2 4GTCTGA s1 3GATATTs2 4G TCTGA score 1 Formconsensus s1 3 2 4 GATCTG arbitrarilybreakties scoresis ProgressiveAlignment ProgressivealignmentisavariationofgreedyalgorithmProgressivealignmentworkswellforclosesequences butitisnotthebestGapsinconsensusstringarepermanentSimplifiedrepresentationofthealignmentsBettersolution Useaprofile ATG CAAAT CCA ACG CTG ClustalW MostpopularmultiplealignmenttooltodaySeveralheuristicstoimproveaccuracy SequencesareweightedbyrelatednessScoringmatrixcanbechosen onthefly Position specificgappenalties ClustalW cont d Oftenusedforproteinalignment W standsfor weighted Differentpartsofalignmentareweighted Position residuespecificgappenalties Three stepprocess1 Pairwisealignment2 BuildGuid