1、4. MORGAN, a decision tree system for gene finding,Integrated system for finding genes in DNA sequences Parse a genomic DNA sequence into coding and non-coding regions. Multi-frame Optimal Rule-based Gene Analyzer Decision Trees (DT) Markov Chains (MC) Dynamic Programming (DP),4.1 The MORGAN framewo

2、rk,Dynamic programming (DP) Optimal parses of a DNA sequence. MC identify Four signal type Start signals Donor sites Acceptor sites Stop codons,4.2 Markov chains to find splice sites,Method for characterizing splice sites Position weight matrix(PWM) Create a table of base probabilities Ex) G and T o

3、ccur with 100% in location 0 and 1 of the intron ( in general, 1/16) Second order Markov chain Compute 64 probabilities ( the probability of each base in each position given the two previous bases) 2000 splice sites is not enough, so use 32 probabilities. Maximal dependence decomposition (MDD) tree,

4、4.3 Parsing DNA with dynamic programming,Gene-finding system using DP Combination with a neural network GeneParser, GRAIL Hidden Markov model Genie, VEIL, GENSCAN Goal of DP Find an optimal segmentation of a DNA sequence into alternating exons and introns,4.3 Parsing DNA with dynamic programming(2),

5、MORGANs DP algorithm At each signal location, keep track of the best parse of the sequence For start site Mark the site and give it a constant score. For donor site End of the first coding exon Search for all matching start codon End of the internal exon Look back for all matching acceptor sites. Sc

6、ore by DT,4.3 Parsing DNA with dynamic programming(3),MORGANs DP algorithm(2) At each acceptor site Scan back in the sequence looking for a matching donor site. At the stop sites Scan back to find the previous acceptor sites, and scores the intervening sequence as a final coding exon. MORGAN saves o

7、nly the best score to store at the new site.,4.4 Frame consistent DP,To guarantee that the parse is optimal, MORGAN must keep track of the best parse at every signal in all three frames. Fig 3. The reason,4.5 Downstream sequence,Important area for future work,5. Data and experiments,570 vertebrate s

8、equences Every sequence contains exactly one gene, and every gene contains at least one intron. All of the introns use standard splicing machinery Training 80%, 454 sequences, 2.3 million bases, 2146 exons Test 114 sequences, 607924 bases, 499 exons Second test set 80% identity to any seuence in the

9、 training set 97 sequences, 566962 bases,Results,Table1 Measures Sensitivity The percentage of true coding bases that the system correctly predicted as coding. Specificity The percentage of the systems predicted coding bases that were actually coding. Ability to locate signals accurately,Results(2),

10、Table 2 Comparison with other gene finders,6. Next step: interpolated Markov models,Glimmer Gene finder in prokarytes Based on interpolate Markov models(IMMs) Combine 0th order 8th order Next step Apply IMMs to the task of exon and intron recognition.,7. Summary,MORGANs strong performance Combination of factors Markov chain models Good at filtering out false signal sites Decision trees Classification of initial(internal, f