CSE182-L8ProjectProject Extra creditProject: Functional annotation of ESTsProject on IndexingHW4Computational Gene FindingGene Finding: The 1st generationCoding versus non-codingGeneralizingA geometric approach (2 hexamers)Choosing between Intergenic and ExonicSlide 135th order markov chainScoring for coding regionsCoding differential for 380 genesOther SignalsCoding region can be detectedSlide 19Combining SignalsThe second generation of Gene findingCombining signals using D.P.Hidden states & gene structureGene finding reformulatedOptimum labeling using D.P. (Viterbi)Optimum parse of the geneSlide 27Slide 28An HMM for Gene structureGeneralized HMMs, and other refinementsLength distributions of Introns & ExonsGeneralized HMM for gene findingForward algorithm for gene findingHMMs and Gene findingDNA SignalsSplice signalsPWMsMDDPowerPoint PresentationMDD for Donor sitesDe novo Gene prediction: SumaryHow many genes do we have?Alternative splicingComparative methodsComparative gene finding toolsDatabasesCSE182-L8Gene FindingProject•EST clustering and assembly•Given a collection of EST (3’/5’) sequences, your goal is to cluster all ESTs from the same gene, and produce a consensus.•Note that all the 3’ ESTs should line up at the 3’ end.•5’ and 3’ ESTs from the same clone should have the same clone ID, which should allow us to recruit them•(Noah, Tim, Jamal, Jesse)InputOutputProject Extra credit•Some genes may be alternatively spliced and may have multiple transcripts•Can you deconvolute the information back from ESTs?ATGProject: Functional annotation of ESTs–Given a collection of ESTs (and assembled transcripts), what is their function?–Use existing databases to annotate the Hirudo ESTs.–Are any protein families under, or over represented?–Specific families (Netrins/Innexins/Phosphatases)Project on Indexing•Indexing•Even if you annotate all ESTs, what is the quick way for someone to search the database to get all Innexins (for example?)•The keyword based index should be able to answer that question•Sergey and DanHW4•Optional/Required?Computational Gene Finding•Given Genomic DNA, identify all the coordinates of the gene•TRIVIA QUIZ! What is the name of the FIRST gene finding program? (google testcode)ATG5’ UTRintronexon3’ UTRAcceptorDonor splice siteTranscription startTranslation startGene Finding: The 1st generation•Given genomic DNA, does it contain a gene (or not)?•Key idea: The distributions of nucleotides is different in coding (translated exons) and non-coding regions.•Therefore, a statistical test can be used to discriminate between coding and non-coding regions.Coding versus non-coding•You are given a collection of exons, and a collection of intergenic sequence.•Count the number of occurrences of ATGATG in Introns and Exons.–Suppose 1% of the hexamers in Exons are ATGATG–Only 0.01% of the hexamers in Intergenic are ATGATG•How can you use this idea to find genes?GeneralizingAAAAAAAAAAACAAAAAGAAAAATI E• Compute a frequency count for all hexamers. • Exons, Intergenic and the sequence X are all vectors in a multi-dimensional space• Use this to decide whether a sequence X is exonic/intergenic.105 2010X105Frequencies (X10-5)A geometric approach (2 hexamers)•Plot the following vectors– E= [10, 20]– I = [10, 5]– V3 = [6, 10]– V4 = [9, 15]•Is V3 more like E or more like I?520151015105EIV3Choosing between Intergenic and Exonic•V’ = V/||V||•All vectors have the same length (lie on the unit circle)•Next, compute the angle to E, and I.•Choose the feature that is ‘closer’ (smaller angle.EIV3€ β€ α€ E - score(V3) =αα + βCoding versus non-coding•Fickett and Tung (1992) compared various measures•Measures that preserve the triplet frame are the most successful.•Genscan: 5th order Markov Model•Conservation across species5th order markov chain•PrEXON[AAAAAACGAGAC..] =T[AAAAA,A] T[AAAAA,C] T[AAAAC,G] T[AAACG,A]……= (20/78) (50/78)………. AAAAAA 20 1AAAAAC 50 10AAAAAG 5 30AAAAAT 3 ..AAAAAAGCAAAAGAAAACEXONScoring for coding regions€ CodingDifferential[ x] = logPrExon[x]PrIntron[x] ⎛ ⎝ ⎜ ⎞ ⎠ ⎟• The coding differential can be computed as the log odds of the probability that a sequence is an exon vs. and intron.•In Genscan, separate transition matrices are trained for each frame, as different frames have different hexamer distributionsCoding differential for 380 genesOther SignalsGTATGAGCodingCoding region can be detectedCoding•Plot the coding score using a sliding window of fixed length.•The (large) exons will show up reliably.•Not enough to predict gene boundaries reliablyOther SignalsGTATGAGCoding•Signals at exon boundaries are precise but not specific. Coding signals are specific but not precise.•When combined they can be effectiveCombining Signals•We can compute the following: –E-score[i,j]–I-score[i,j]–D-score[i]–I-score[i]–Goal is to find coordinates that maximize the total scorei jThe second generation of Gene finding•Ex: Grail II. Used statistical techniques to combine various signals into a coherent gene structure.•It was not easy to train on many parameters. Guigo & Bursett test revealed that accuracy was still very low.•Problem with multiple genes in a genomic regionCombining signals using D.P.•An HMM is the best way to model and optimize the combination of signals•Here, we will use a simpler approach which is essentially the same as the Viterbi algorithm for HMMs, but without the formalism.Hidden states & gene structure•Identifying a gene is equivalent to labeling each nucleotide as E/I/intergenic etc.•These ‘labels’ are the hidden states•For simplicity, consider only two states E and IIIIIIEEEEEEIIIIIIEEEEEEIIIIEEEEEE IIIIIi1i2i3i4Gene finding reformulated•Given a labeling L, we can score it as •I-score[0..i1] + E-score[i1..i2] + D-score[i2+1] + I-score[i2+1..i3-1] + A-score[i3-1] + E-score[i3..i4] + …….•Goal is to compute a labeling with maximum score.IIIIIEEEEEEIIIIIIEEEEEEIIIIEEEEEE IIIIIi1i2i3i4Optimum labeling using D.P. (Viterbi)•Define VE(i) = Best score of a labeling of the prefix 1..i such that the i-th position is labeled E•Define VI(i) = Best score of a labeling of the prefix 1..i such that the i-th position is labeled I•Why is it enough to compute VE(i) & VI(i) ?Optimum parse of the gene € VE(i) = maxj<iE_score[ jK i] + VI( j −1)+A_score[ j