Phylogenetic Hidden Markov Models

Description

Niveau: Supérieur, Doctorat, Bac+8
12 Phylogenetic Hidden Markov Models Adam Siepel1 and David Haussler2 1 Center for Biomolecular Science and Engineering, University of California, Santa Cruz, CA 95064, USA, 2 Center for Biomolecular Science and Engineering, University of California, Santa Cruz, CA 95064, USA, Phylogenetic hidden Markov models, or phylo-HMMs, are probabilistic mod- els that consider not only the way substitutions occur through evolutionary history at each site of a genome but also the way this process changes from one site to the next. By treating molecular evolution as a combination of two Markov processes—one that operates in the dimension of space (along a genome) and one that operates in the dimension of time (along the branches of a phylogenetic tree)—these models allow aspects of both sequence structure and sequence evolution to be captured. Moreover, as we will discuss, they per- mit key computations to be performed exactly and e?ciently. Phylo-HMMs allow evolutionary information to be brought to bear on a wide variety of problems of sequence “segmentation,” such as gene prediction and the iden- tification of conserved elements. Phylo-HMMs were first proposed as a way of improving phylogenetic mod- els that allow for variation among sites in the rate of substitution [9, 52]. Soon afterward, they were adapted for the problem of secondary structure predic- tion [11, 47], and some time later for the detection of recombination events [20].

• distribution associated


• phylogenetic models


• qj has


• current state


• sequence


• state probabilities


• hmms


• models can


• markov models


• state phylo-hmm

Sujets

• Markov model

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 14
• Langue: English

Extrait

21 PhylogeneticHiddenMarkovModels AdamSiepel 1 andDavidHaussler 2 1 CenterforBiomolecularScienceandEngineering, UniversityofCalifornia,SantaCruz,CA95064,USA, [e-mail] 2 CenterforBiomolecularScienceandEngineering, UniversityofCalifornia,SantaCruz,CA95064,USA, [e-mail] PhylogenetichiddenMarkovmodels,orphylo-HMMs,areprobabilisticmod- elsthatconsidernotonlythewaysubstitutionsoccurthroughevolutionary historyateachsiteofagenomebutalsothewaythisprocesschangesfrom onesitetothenext.Bytreatingmolecularevolutionasacombinationof twoMarkovprocesses—onethatoperatesinthedimensionofspace(alonga genome)andonethatoperatesinthedimensionoftime(alongthebranches ofaphylogenetictree)—thesemodelsallowaspectsofbothsequencestructure andsequenceevolutiontobecaptured.Moreover,aswewilldiscuss,theyper- mitkeycomputationstobeperformedexactlyandefficiently.Phylo-HMMs allowevolutionaryinformationtobebroughttobearonawidevarietyof problemsofsequence“segmentation,”suchasgenepredictionandtheiden- tificationofconservedelements. Phylo-HMMswerefirstproposedasawayofimprovingphylogeneticmod- elsthatallowforvariationamongsitesintherateofsubstitution[9,52].Soon afterward,theywereadaptedfortheproblemofsecondarystructurepredic- tion[11,47],andsometimelaterforthedetectionofrecombinationevents[20]. Recentlytherehasbeenarevivalofinterestinthesemodels[41,42,43,44,33], inconnectionwithanexplosionintheavailabilityofcomparativesequence data,andanaccompanyingsurgeofinterestincomparativemethodsforthe detectionoffunctionalelements[5,3,24,46,6].Therehasbeenparticular interestinapplyingphylo-HMMstoamultispeciesversionoftheabinitio genepredictionproblem[41,43,33]. Inthischapter,phylo-HMMsareintroduced,andexamplesarepresented illustratinghowtheycanbeusedbothtoidentifyregionsofinterestinmul- tiplyalignedsequencesandtoimprovethegoodnessoffitofordinaryphylo- geneticmodels.Inaddition,wediscusshowhiddenMarkovmodels(HMMs), phylogeneticmodels,andphylo-HMMsallcanbeconsideredspecialcasesof general“graphicalmodels”andhowthealgorithmsthatareusedwiththese modelscanbeconsideredspecialcasesofmoregeneralalgorithms.Thischap- teriswrittenatatutoriallevel,suitableforreaderswhoarefamiliarwith phylogeneticmodelsbuthavehadlimitedexposuretootherkindsofgraphi- calmodels.

326A.SiepelandD.Haussler 12.1Background Aphylo-HMMcanbethoughtofasamachinethatprobabilisticallygenerates amultiplealignment,columnbycolumn,suchthateachcolumnisdefinedby aphylogeneticmodel.Aswiththesingle-sequenceHMMsordinarilyusedin biologicalsequenceanalysis[7],thismachineprobabilisticallyproceedsfrom onestatetoanother 1 ,andateachtimestepit“emits”anobservableob- ject,whichisdrawnfromthedistributionassociatedwiththecurrentstate (Figure12.1).Withphylo-HMMs,however,thedistributionsassociatedwith statesarenolongermultinomialdistributionsoverasetofcharacters(e.g., { A,C,G,T } )butaremorecomplexdistributionsdefinedbyphylogeneticmod- .sle Phylogeneticmodels,asconsideredhere,defineastochasticprocessofsub- stitutionthatoperatesindependentlyateachsiteinagenome.(Thequestion ofindependencewillberevisitedbelow.)Intheassumedprocess,acharacter isfirstdrawnatrandomfromthebackgrounddistributionandassignedtothe rootofthetree;charactersubstitutionsthenoccurrandomlyalongthetree’s branchesfromroottoleaves.Thecharactersthatremainattheleaveswhen theprocesshasbeencompleteddefineanalignmentcolumn.Thus,aphyloge- neticmodelinducesadistributionoveralignmentcolumnshavingacorrela- tionstructurethatreflectsthephylogenyandsubstitutionprocess(see[11]). Thedifferentphylogeneticmodelsassociatedwiththestatesofaphylo-HMM mayreflectdifferentoverallratesofsubstitution(asinconservedandnoncon- servedregions),differentpatternsofsubstitutionorbackgrounddistributions (asincodingandnoncodingregions),orevendifferenttreetopologies(aswith recombination[20]). TypicallywithHMMs,asequenceofobservations(heredenotedX)is availabletobeanalyzed,butthesequenceofstates(calledthe“path”)by whichtheobservationsweregeneratedis“hidden”(hencethename“hidden Markovmodel”).Efficientalgorithmsareavailabletocomputethemaximum- likelihoodpath,theposteriorprobabilitythatanygivenstategeneratedany givenelementof X ,andthetotalprobabilityof X consideringallpossible paths(thelikelihoodofthemodel).TheusefulnessofHMMsingeneral,and phylo-HMMsinparticular,isinlargepartaconsequenceofthefactthat thesecomputationscanbeperformedexactlyandefficiently.Inthischapter, threeexamplesofapplicationsofphylo-HMMswillbepresentedthatpar- allelthesethreetypesofcomputation—predictionbasedonthemaximum- likelihoodpath(Example12.1),predictionbasedonposteriorprobabilities (Example12.2),andimprovedgoodnessoffit,asevidencedbymodellikeli- hood(Example12.3).Finally,itwillbeshownhowthesealgorithmsmaybe consideredspecialcasesofmoregeneralalgorithmsbyregardingphylo-HMMs asgraphicalmodels. 1 Throughoutthischapter,itisassumedthattheMarkovchainforstatetransi- tionsisdiscrete,first-order,andhomogeneous.