RNA Secondary Structure Prediction

RNASecondaryStructurePrediction DynamicProgrammingApproachesSarahAerni http www tbi univie ac at Outline RNAfoldingDynamicprogrammingforRNAsecondarystructurepredictionCovariancemodelforRNAstructureprediction RNABasics RNAbasesA C G UCanonicalBasePairsA UG CG U wobble pairingBasescanonlypairwithoneotherbase Image http www bioalgorithms info 2HydrogenBonds 3HydrogenBonds morestable RNABasics transferRNA tRNA messengerRNA mRNA ribosomalRNA rRNA smallinterferingRNA siRNA microRNA miRNA smallnucleolarRNA snoRNA http www genetics wustl edu eddy tRNAscan SE RNASecondaryStructure Hairpinloop Junction Multiloop BulgeLoop Single Stranded InteriorLoop Stem Image Wuchty Pseudoknot SequenceAlignmentasamethodtodeterminestructure BasespairinordertoformbackbonesanddeterminethesecondarystructureAligningbasesbasedontheirabilitytopairwitheachothergivesanalgorithmicapproachtodeterminingtheoptimalstructure BasePairMaximization DynamicProgrammingAlgorithm SimpleExample MaximizingBasePairing Basepairatiandj Unmatchedati Umatchedatj Bifurcation Images SeanEddy S i j isthefoldingofthesubsequenceoftheRNAstrandfromindexitoindexjwhichresultsinthehighestnumberofbasepairs BasePairMaximization DynamicProgrammingAlgorithm AlignmentMethodAlignRNAstrandtoitselfScoreincreasesforfeasiblebasepairsEachscoreindependentofoverallstructureBifurcationaddsextradimension Initializefirsttwodiagonalarraysto0 Fillinsquaressweepingdiagonally Images SeanEddy Basescannotpair similartounmatchedalignment S i j 1 Basescanpair similartomatchedalignment S i 1 j DynamicProgramming possiblepaths S i 1 j 1 1 BasePairMaximization DynamicProgrammingAlgorithm AlignmentMethodAlignRNAstrandtoitselfScoreincreasesforfeasiblebasepairsEachscoreindependentofoverallstructureBifurcationaddsextradimension Initializefirsttwodiagonalarraysto0 Fillinsquaressweepingdiagonally Images SeanEddy Reminder ForallkS i k S k 1 j k 0 BifurcationmaxinthiscaseS i k S k 1 j Reminder ForallkS i k S k 1 j Basescannotpair similar Basescanpair similartomatchedalignment DynamicProgramming possiblepaths Bifurcation addvaluesforallk BasePairMaximization Drawbacks BasepairmaximizationwillnotnecessarilyleadtothemoststablestructureMaycreatestructurewithmanyinteriorloopsorhairpinswhichareenergeticallyunfavorableComparabletoaligningsequenceswithscatteredmatches notbiologicallyreasonable EnergyMinimization ThermodynamicStabilityEstimatedusingexperimentaltechniquesTheory MostStableistheMostlikelyNoPseudknotsduetoalgorithmlimitationsUsesDynamicProgrammingalignmenttechniqueAttemptstomaximizethescoretakingintoaccountthermodynamicsMFOLDandViennaRNA EnergyMinimizationResults LinearRNAstrandfoldedbackonitselftocreatesecondarystructureCircularizedrepresentationusesthisrequirementArcsrepresentbasepairing Images DavidMount Allloopsmusthaveatleast3basesinthemEquivalenttohaving3basepairsbetweenallarcs Exception LocationwherethebeginningandendofRNAcometogetherincircularizedrepresentation TroublewithPseudoknots PseudoknotscauseabreakdownintheDynamicProgrammingAlgorithm Inordertoformapseudoknot checksmustbemadetoensurebaseisnotalreadypaired thisbreaksdowntherecurrencerelations Images DavidMount EnergyMinimizationDrawbacks ComputeonlyoneoptimalstructureUsualdrawbacksofpurelymathematicalapproachesSimilardifficultiesinotheralgorithmsProteinstructureExonfinding AlternativeAlgorithms Covariaton IncorporatesSimilarity basedmethodEvolutionmaintainssequencesthatareimportantChangeinsequencecoincidestomaintainstructurethroughbasepairs Covariance Cross speciesstructureconservationexample tRNAManualandautomatedapproacheshavebeenusedtoidentifycovaryingbasepairsModelsforstructurebasedonresultsOrderedTreeModelStochasticContextFreeGrammar ExpectareasofbasepairingintRNAtobecovaryingbetweenvariousspecies BasepairingcreatessamestabletRNAstructureinorganisms Mutationinonebaseyieldspairingimpossibleandbreaksdownstructure CovariationensuresabilitytobasepairismaintainedandRNAstructureisconserved BinaryTreeRepresentationofRNASecondaryStructure RepresentationofRNAstructureusingBinarytreeNodesrepresentBasepairiftwobasesareshownLoopifbaseand gap dash areshownPseudoknotsstillnotrepresentedTreedoesnotpermitvaryingsequencesMismatchesInsertions Deletions Images Eddyetal CovarianceModel HMMwhichpermitsflexiblealignmenttoanRNAstructure emissionandtransitionprobabilitiesModeltreesbasedonfinitenumberofstatesMatchstates sequenceconformstothemodel MATP StateinwhichbasesarepairedinthemodelandsequenceMATL MATR StateinwhicheitherrightorleftbulgesinthesequenceandthemodelDeletion StateinwhichthereisdeletioninthesequencewhencomparedtothemodelInsertion StateinwhichthereisaninsertionrelativetomodelTransitionshaveprobabilitiesVaryingprobability Enterinsertion remainincurrentstate etcBifurcation noprobability describespath CovarianceModel CM TrainingAlgorithm S i j ScoreatindicesiandjinRNAwhenalignedtotheCovarianceModel Independentfrequencyofseeingthesymbols A C G T inlocationsiorjdependingonsymbol Frequenciesobtainedbyaligningmodelto trainingdata consistsofsamplesequencesReflectvalueswhichoptimizealignmentofsequencestomodel Frequencyofseeingthesymbols A C G T togetherinlocationsiandjdependingonsymbol AlignmenttoCMAlgorithm CalculatetheprobabilityscoreofaligningRNAtoCMThreedimensionalmatrix O n AlignsequencetogivensubtreesinCMForeachsubsequencecalculateallpossiblestatesSubtreesevolvefromBifurcationsForsimplicityLeftsingletisdefault Images Eddyetal ForeachcalculationtakeintoaccounttheTransition T tonextstateEmissionprobability P inthestateasdeterminedbytrainingdata Bifurcation doesnothaveaprobabilityassociatedwiththestate Deletion doesnothaveanemissionprobability P associatedwithit Images Eddyetal Alignme