BIO/CSC295 2011F, Class 13: Gene Prediction (1) Overview: * SamR shouldn't leave his computer logged in because CF can do ~exciting~ things * Quick review: Shortest Superstring. * Check in: What is a gene? * Gene Prediction: Going beyond DNA. * Strategies for predicting useful ORFs. * Obstacles to finding genes. * Detour: Why Sam loves this topic. * Web exploration. * Programming exploration. Admin: * Chase will have office hours on Sunday night 8-11PM. Come if you want to review. * HIV responses sent via email. If you did not get one, you are marked as having a zero, so you should probably contact V. Praitis. * RK, who has no COI, says last chance to get cheap good cupcakes at bookstore! * Response to Kellis et al. is due Tuesday. * Tonight is homecoming in Grinnell. If you've never seen a small-town Iowa homecoming parade, it's worth going at least once. (Today at 5:30) * If you must partake of 10/10 this weekend, please partake responsibly. * Today's programming lab is your next programming assignment, and is due Thursday. * EC for Today's CS extra on Computer Vision (4:30, 3821). * EC for Friday's Biology Seminar: MC and two other people, how cells respond to stroke (but in comlpicated terms) (noon, 2021). * EC for Healthy Iowa Walk noon on Friday. * Start outside of JRC. * Don't forget to sign up for the blueiowa thingy. Sam or Vida will send out email. * Followup on study of healthy countries - Adopt their procedures * EC for Danforth lecture (today at 4:15, you're smart enough to figure out where) * EC for Friday's Volleyball game (7pm, Darby). * EC for Saturday's Football game (1 pm). * EC for Saturday's Volleyball game (1pm, Darby). * EC for Saturday's Men's Soccer game (1:30 pm). * EC for Orchestra, Saturday (2pm, S-L). We had been discussing the shortest superstring problem. * We approximate the shortest superstring * Input: set of strings * Output: single string * Contains all of the individual strings * Relatively short * Technique: Keep a running "superstring" and a set of strings left to process start with the longest string; look for best alignment with remaining strings;repeat! what has the most overlap with next one; new S Eventually we will have gone through all sequences. Program allows overlap in each direction. Sometimes, picking one good overlap will prevent a better overlap that comes up later SAA AAL becomes SAAL; later AAA; doesn't fit AAA could actually fit in the middle Original algorithm was to try this in every order Variant! Instead of always having one string - you align some strings with each other that don't align in the main string Start with all the strings - look for the pair that align best S1 and S24 S1,24 then goes into set S2, S23 align to S2,23 this goes back into set We end up with one larger string or several that don't align with each other Basic strategy (but maybe a little more clever than this second strategy) recall: fragments input are overlapping (e.g. you use different restriction enzymes to get fragments). NIH - statements about reprod. of bio algorithms. What is a gene? * A DNA sequence that codes for a mRNA sequence that codes for an amino acid sequence that produces a protein (or part of a protein). * Or can produce multiple proteins, depending on splicing * Biological magic can chop out parts when building the mRNA (we keep the exons and chop out the introns) * Or can encode functional RNA, including transcriptional RNAs and micro RNAs. * Micro RNAs are really imporant, but we have only crude understanding of how they are structured. * Note genes are inheritable * Genes have promoters and other sequences involved in regulation * Promoter helps determine how gene is transcribed. * Molecular machinery recognizes particular sequences. * Other regulation happens around exons and introns to help with splicing * And more regulation happens with upstream stuff: When things bind there, transcription can happen. (These are transcription factors.) * When should it be expressed and in what cell types * Regulatory sequences are VERY important * Genes have a start sequence and terminators that end the sequence. Problem: We have the lovely sequences created by shotgun assembly or more reliable techniques. 3 billion base pairs. * Identify start sequences * Open Reading Frame (ORF) * Identify terminators * Are they real or not? * Complicating the world: introns don't have lengths in multiples of 3 * We know some characteristics of ORFs: E.g., likely minimum and maximum size. * We've seen some that are 30-50 base pairs * We've seen some that are thousands of base pairs * That start sequence occurs a LOT in the 3 billion base pairs 22/1000 = 66 million start sequences * We have substantially fewer genes * Fortunately, there are common promoter sequences * It may be easier to find a *class* of genes (common promoter) than a single gene * Shine-Dalgarno is conserved pretty well in bacteria * And it's all a probabalistic algorithm * Question: Can you have a gene within a gene? * It depends on what you mean. * You are unlikely to have a gene within an exon. * It has certainly happened that genes have been found within introns * And remember that genes code in both directions. * Biology is messy: "What is coding and noncoding can change all the time" - V. Praitis * Question: How can a terminator not be real? * If it's not in the right reading frame. * If it's in the intron. * How do we predict intron/exon boundaries? What do we know about them? * Only probablistic stuff * And not enough * introns almost always start with GT and then AAGT * But those A's can be G's (or maybe even C's and T's) * introns almost always end with (TC)(CTAG)(CT)AG * Grinnell trivia: Tom Cech figured out the chemistry of splicing * Because there is lots of probabalistic stuff here, some people use Hidden Markov Models * Probabalistic magic: You put in lots of known things, and the HMM "figures out a pattern" * Don't worry, we won't make you implement them, unless you are a Math/Stats major * How good are gene finder programs? * Need to worry about false positives as well as unidentifie dgenes * The best programs are only at about 30% for raw sequence information * Extracting info from a naked DNA sequence is hard * So what other techniques can we use? * Look at similar organisms. Of course, that assumes that you have data for those organisms. * Where there are genes in one and high sequence conservation, you are likely to have genes in the other. * Kellis does this. "It's breathtaking." -- V. Praitis * We'll miss the things that make you a unique species. * It's a chicken and egg problem. Where do the genes in the previous organism come from? * Find out what genes are expressed and then go backwards. * Can we find out sequences from proteins? * Well, mass spec helps a bit, but you normally need to have a predicted sequences * Look at the mRNA! * Trick for purifying mRNA. All have a poly-A tail. * Column with lots of poly-T. Catches mRNA. Extract. * Reverse transcriptase. Convert back to DNA. Align. * A problem: Tons of work. * A minor problem: Need to do some work to go from mRNA back to full DNA sequence with exons and introns * Another problem: Biases in building a library; not all genes are being expressed at the same time; some are rarely expressed * You will miss some things pretty regularly * Another problem: You will miss other kinds of RNA: tRNA, ribosomal RNAs; mRNAs are less than 10%. miRNAs. * Detour miRNAs: About 30 nucleotides. Fold into structures and get cleaved. Complementary to other genes. Cause degredation of message or block message. * First discovered in 1990's. * Second not discovered for another decade. * Then we realized that they're all over the place and they are crucial for gene regulation. * Someone will get a Nobel prize for this * And then you can look for patterns. Comments and Questions * Patterns, such as high or low coding frequency. * E.g., coding sequences are AC rich, codon usage bias * Codon bias: Although two or four codons code for the same AA, in a particular species, we are more likely to see one of the codons than the others. * All of these are probabalistic This is Sam's favorite part of bioinformatics * Clearly an open problem * Solutions require collaboration Biologist: Hypothetical approach Computer scientist: Build program Biologist: Consider results * Example: Olfactory genes Labs: * Form a mixed group * Do as much as you can on the Web exploration until 2:45 * Do as much as you can on the programming exploration until 3:05 * Continue to work on the programming exploration on your own