MORGAN, a decision tree system for gene finding

《MORGAN, a decision tree system for gene finding》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、4.MORGAN,adecisiontreesystemforgenefindingIntegratedsystemforfindinggenesinDNAsequencesParseagenomicDNAsequenceintocodingandnon-codingregions.Multi-frameOptimalRule-basedGeneAnalyzerDecisionTrees(DT)MarkovChains(MC)DynamicProgramming(DP)4.1TheMORGANframeworkDynamicprogramming(DP)Opti

2、malparsesofaDNAsequence.MCidentifyFoursignaltypeStartsignalsDonorsitesAcceptorsitesStopcodons4.2MarkovchainstofindsplicesitesMethodforcharacterizingsplicesitesPositionweightmatrix(PWM)CreateatableofbaseprobabilitiesEx)GandToccurwith100%inlocation0and1oftheintron(ingeneral,1/16)Second

3、orderMarkovchainCompute64probabilities(theprobabilityofeachbaseineachpositiongiventhetwopreviousbases)2000splicesitesisnotenough,souse32probabilities.Maximaldependencedecomposition(MDD)tree4.3ParsingDNAwithdynamicprogrammingGene-findingsystemusingDPCombinationwithaneuralnetworkGenePa

4、rser,GRAILHiddenMarkovmodelGenie,VEIL,GENSCANGoalofDPFindanoptimalsegmentationofaDNAsequenceintoalternatingexonsandintrons4.3ParsingDNAwithdynamicprogramming(2)MORGAN’sDPalgorithmAteachsignallocation,keeptrackofthebestparseofthesequenceForstartsiteMarkthesiteandgiveitaconstantscore.F

5、ordonorsiteEndofthefirstcodingexonSearchforallmatchingstartcodonEndoftheinternalexonLookbackforallmatchingacceptorsites.ScorebyDT4.3ParsingDNAwithdynamicprogramming(3)MORGAN’sDPalgorithm(2)AteachacceptorsiteScanbackinthesequencelookingforamatchingdonorsite.AtthestopsitesScanbacktofin

6、dthepreviousacceptorsites,andscorestheinterveningsequenceasafinalcodingexon.MORGANsavesonlythebestscoretostoreatthenewsite.4.4FrameconsistentDPToguaranteethattheparseisoptimal,MORGANmustkeeptrackofthebestparseateverysignalinallthreeframes.Fig3.Thereason4.5DownstreamsequenceImportanta

7、reaforfuturework5.Dataandexperiments570vertebratesequencesEverysequencecontainsexactlyonegene,andeverygenecontainsatleastoneintron.AlloftheintronsusestandardsplicingmachineryTraining80%,454sequences,2.3millionbases,2146exonsTest114sequences,607924bases,499exonsSecondtestset80%identit

8、ytoanyseuenc