BIO/CSC295 2011F, Class 14: Gene Prediction (2) Overview: * Kellis et al. 2003. * Exam Policies. * Exam Review. * Questions on Sample Exam. Admin: * Bio SEPC Survey. See instructions on the sheet. * Don't forget that Project 6.5 is due on Thursday. * Don't forget that the exam is on Thursday! * EC for Panel Discussion on the Future of the Book, Thursday, 4:15, in Faulconer. * EC for Volleyball Friday at 7:00 p.m. in Darby. * Scarlet night. Buy a t-shirt. * Answer trivia questions about the senior volleyballers * If they win, they go on to regionals * So DON'T LEAVE TOWN UNTIL SATURDAY (or after) * EC for Volleyball Saturday at 11:00 a.m. and 3:00 p.m. in Darby. Kellis! * Eric Lander is a Mathematician who switched over to BioSci to work on the Human Genome project. A role model. * But Kellis is a big-hat guy, too. * General impressions? * A lot of information in the paper * A lot of work - Mistakes in the published genome, more genes, etc. * LONG! It took "forever" to read. * What's the goal of the paper? * A new method for finding important parts of the genome * Compare sequences to help find important parts * Use close sequences so that most genes would be conserved, but non-coding stuff would be less conserved. * Evolutionary theory: Important things are conserved, less important things need not be conserved. * What species? Yeast. S. cervisiae * Sequenced * Well understood - lots of exprssion data * A way to analyze the value of your results * Lets you do the functional stuff better * "The best characterized Eucaryotic organism" * Comparatively few introns for a Eucaryotic organism - a relatively simple gene structure. * Likely to find related species that fit desired parameters * Short generation times - rapid evolution * Why model system? * Everywhere and easy to grow and store. You can freeze it and thaw it. * Gene dense. * Does that make it easier or harder? * Methodology * Four yeast species that fit evolution criteria * S. cervisiae already sequenced * But they need to sequence the others * Shotgun sequencing * And reassemble. (YOU could do this.) * NOT complete coverage; about 95%. * Not really answered * They use hedge words like "adequate" * A critique of the paper: What are there criteria for "adequate"? Do they state it clearly? * Align the sequences and partial sequences * Using big ORFs (minimum 300) * Align them all * Some align well, some don't * Some align 1-1 * Some don't align to anything * Some align ambiguously * Doesn't seem perfect, but it's not clear that there's a better method. * How do they turn the individual alignments into a global alignment? (Or do they start with a global alignment) * So, what's figure 1 all about? * After global alignment, they look at how well the individual ORFs align. * Most of the rearrangement happens in the telomeres - the regions at the end of the chromosome * Evidence from multiple species that there's much more recombination and rearrangement at the ends of chromosomes * Rearrangement not uniformly distributed * Middle more important for key genes; Ends more important for speciation * Factoid: Where do rearrangements happen? Particularly inversions. * Mostly in tRNA genes * Not randomly across the geneome * Transposons can move around * A test to determine whether an ORF is biologically meaningful * Assign a "score" * Question: Do others use the same test? Why did they use this test? * A core aspect of the paper. * Proof that the technique works well. * See Figure 4 * This paper is a model of bioinformatics * A *lot* of time (bench work) spent on S. cervisiae * If this technique works, we can potentially avoid a lot of the bench work, and that's incredible. * How do they decide whether or not the ORFs are genes? * Is it enough to line them up and see "the ghosts of yeasts past"? * Can check their answers based on what people have already identified. * Is that good enough? * Has someone applied this to other domains? * Yes, VP has seen it done for Drosophila * And they argued that the algorithm is *more* reliable for bigger genomes * Well, a modified version. * What about regulatory sequences / motifs? * These are harder to discern. * Do you need a catalog? * Yes. * You can start with theirs, but would want to add others. * Suspicious that they discovered more new regulatory sequences than known regulatory sequences * May be biased toward certain kinds of regulatory sequences * We also know very little about regulatory sequences in the field * Requires a *lot* of work * So very few researchers study it careful * Instead, we're lazy and just choose some upstream stuff. * Abstraction is difficult; Lab analysis is expensive; So this seems like a good place to start. Criticisms * Many things left unanswered, and for the yeast community to address * Unclear criteria for "adequate" * How generalizable is this? What if you don't have something like S. Cervisiae? * There's a lot of validation happening here. * Can this be used on other species that we have not done regulatory work on? Do we need a characterized genome? * Some of us find this convincing for yeast genomes * What about non-yeast genomes? * The intron/exon thing may invalidate the algorithm * Or ... a positive result from this algorithm in humans is unlikely, so something it says is a gene is more likely to be a gene * Does more junk/noise increase the likelihood of false positives or false negatives? * Let's try it and find out! * Biased towards longer genes. * Since they don't know about it, should they really have mentioned the human genome. * Assembly problem is much more difficult * What about repeat sequences? * "A human genome has a much lower signal-to-noise ration" Thursday's exam. * In class. * No computer. (We discussed it, and time to solve computer-based problems seems remarkably inconsistent.) * You may bring one page of notes. (8.5x11, double sided.) * Designed to take under ninety minutes, so that you'll have enough time. * For Python: You will not need to write working code. You may need to read code. You may need to write code. You may need to explain how to modify code. * Six problems (some with subproblems) * Out seven. Review Format * The exam is based on the first six chapters of our textbook, and the four sets of readings that we've done (Dinosaur Protein, HIV, BLAST, Kellis). * Rather than giving you a list of topics, we'll start by going around the room, identifying and categorizing topics that we've studied this semester. * Praitis and Rebelsky will fill in any topics they think are missing. * We'll then continue by discussing any of the topics for which you feel you need some review. Primary Categories: * Biological Frameworks * Underlying biological concepts: Base pair, Gene, * Regulatory elements in the genome * Antibiotics and horizonatal and vertical gene transfer * DNA sequencing * Including Sanger sequencing * Generalized through directed sequencing and shotgun sequencing * Central Dogma * ORF * Conservation of biologically important sequences * Introns and Exons * Categorizing amino acids * Hydrophobic or Hydrophillic * Charges (negative or positive) * Shape * Inheritance patterns: Dominant/Recessive * Genetic tradeoffs * How viruses mutate * cDNA libraries (from RNA to cDNA using the enzyme reverse transcriptase) * Model organisms and why we care about them * Brewers/Baker's yeast * Vida's worm * Fruit flies * Humans * Key Bioinformatics Algorithms and Concepts * Needleman-Wunsch and alignment grids * BLAST * The PAM Matrix and other substitution matrices * And choosing one * Gene and ORF finding * Align sequences and compare sequences * DNA * Protein * Translations, e.g., from DNA to AA sequences or from DNA to complement * Reassembly of shotgun sequences - Shortest Superstring * Sorting algorithms * Bioinformatics Tools (e.g., at NCBI) * BLAST * ClustalW * Searching using NCBI * Fasta File Format * Local and global alignment * Programming in Python * How to write a function * For loops * Lists and strings * Research Papers * Dinosaur Proteins - Techniques for potentially identifying proteins in fossil material. How do we do this? Mass spec. * Kellis teaches us about ... * Other * NP Complete Problems * Pipettemen * You participate more if you sit in the front of the room * Sometimes it's necessary to calculate approximations rather than the exact value because "CS is messy" * An approach to reading papers * Always look for potential flaws and decide how significant they are * Philosophical questions * Why do bioinformatics? * What is bioinformatics? * Who can do bioinformatics? * What kinds of questions can bioinformatics answer? Key things to talk about * BLAST. Parameters * w - word length * T - threshold for words * S - threshold for 'matching sequences' Precomputation (using database): * Identify high-scoring words: * Length w * Score of >= T when matched against themselves * Identify positions of close matches to high-scoring words For any word: a list of [dbelement,pos,score] All of the scores are >= T Search (using search string and precomputed stuff): * Identify high scoring words in search string * Extract positions of close matches using the precomputed stuff * Expand each close match in both directions until you lose too much (20) by expanding * Return all expanded things that have a score >= S. * Needleman-Wunsch * Given two strings S1, S2, find best alignment * Including deletions, insertions, matches, mismatches, and mutations * Table Entry i, j gives a. The score of the best alignment of S1[0:i] to S2[0:j] b. It gives information about how to get that alignment (in practice we use a separate table for this). Goal is to produce the table/pair of tables Initially - you give a set of values to compare string to empty string Fill in the initial boxes For each box, what is the best choice? Delete 1, delete other, match Cost for deleting; score to match Select best (the one with the highest score) Do the same computation in each cell match score DNA or for proteins PAM score Apply the same action for each box. * Terminology * That's why you can bring a cheat sheet. * Vida will be slightly sympathetic to non-biologists who can't remember stuff like "plasmid" Questions on the Sample Exam