1Today•Midterm• Project proposals are due Thursday– A brief review of citation practices• Introduction to Hidden Markov ModelsMidterm gradesMidterm exam distribution: Max: 91%, Min: 63%, Mean: 78.5%Total midterm score = (ΣiPS(i) + 0.6 * midterm score)/140Midterm score distribution:Max: 94%, Min: 75%, Mean: 85%A: > 90%B: 80% - 90%B-, C+: < 80%Midterm 1a) As a preprocessing step for sequence assembly, it is necessary to identify pairs of DNA sequence fragments that overlap. Let T and U be two sequence fragments. We wish to determine whether the end of T overlaps with the beginning of U.– Semiglobal alignment– Can use similarity or distance scoring1b) Given the operations insertion, deletion and substitution, the problem is to determine the minimum number of operations required to transform T into U.– Global alignment– To count operations, you must use edit distance:• s[i,j] = 1, if i ≠ j,• s[i,i] = 0, • g = 121c) T and U are genomic DNA sequences containing the albumin gene, in mouse and human, respectively. We wish to find the intron/exon boundaries of the albumin gene in the genomic DNA.– Local alignment– Constraints:• s[i,j] must be a similarity function• s[i,i] > s[i,j] > 2g• Expected random alignment must be negative• At least one, s[i,i] must be positive.ACGTSP = 6 TA = 3 Sum of PairsTree alignmentTGCAATCGACProblem 2 (a and b)Problem 3c) Maximum likelihood considers all possible internal labels when scoring a tree: O(|Σ|k). With an alphabet that is twice the size of Σ, the running time will be proportional to |2Σ|k , i.e., increased by a factor of 2k .This is why maximum likelihood is used more for DNA than amino acid sequencesd) Both maximum likelihood and parsimony use character data. Both maximum likelihood and distance based methods assume a model of neutral evolution.Problem 3c) Species: bacterium, archaebacterium and two vertebrates. Data is an ultrametric distance matrix¾ Use UPGMA or midpoint rooting. Note there is no obvious out group for these species. d) Data: immunoglobulin sequences for four old world monkeys¾ Immunoglobulin sequences mutate rapidly, so use NJ or maximum likelihood. Root with an outgroup, e.g., a new world monkey or an ape sequence.e) Data: ribosomal sequences in closely related species.¾ Both maximum parsimony or maximum likelihood will infer ancestral sequences, but maximum parsimony is a better model for slowly evolving sequences in closely related species.3Problem 4a) The distances came from a tree, so you didn’t have to check the four point condition.c) According to the tree distances, are the four taxa changing at the same rate. The tree distances are additive, but fail the 3pt condition so they are not ultrametric. Therefore they are not changing at the same rate.e) Data: ribosomal sequences in closely related species.¾ Both maximum parsimony or maximum likelihood will infer ancestral sequences, but maximum parsimony is a better model for slowly evolving sequences in closely related species.Today•Midterm• Project proposals are due Thursday– A brief review of citation practices• Introduction to Hidden Markov ModelsWhy cite?• Citations reflect the careful and thorough work you have put in to locating and exploring your sources. • Citations help readers understand the context of your argument, and locate your work within other conversations on your topic. • Citations allow you to acknowledge those authors who made possible particular aspects of your work. Failure to provide adequate citations constitutes plagiarism. • Citations, by delineating your intellectual debts, also draw attention to the originality and legitimacy of your own ideas. http://www.dartmouth.edu/~sources/about/what.htmlWhen to cite?• Cite sources for all verbatim quotations of two or more consecutive words.• Cite sources from which you paraphrase or summarize facts or ideas.• Cite sources for ideas or information that could be regarded as common knowledge but which you think your reader might still find unfamiliar.http://www.dartmouth.edu/~sources/about/what.html4What to cite?Primarily: refereed, archival materials. (Archival materials are materials that are available in libraries or bookstores, have an ISBN number, etc.)• Books• Journal articles• Refereed conference proceedingsAvoid: • Websites, news stories, photocopied workshop handouts, personal communications.The original text:The main image in Othello is that of animals in action, preying upon one another, mischievous, lascivious, cruel or suffering, and through these, the general sense of pain and unpleasantness is much increased and kept constantly before us. More than half the animal images in the play are Iago's, and all these are contemptuous or repellent: a plague of flies, a quarrelsome dog, the recurrent image of bird-snaring, leading asses by the nose, a spider catching a fly, beating an offencelessdog, wild cats, wolves, goats and monkeys1.1. Caroline F. E. Spurgeon, Shakespeare's Imagery (Cambridge: Cambridge UP, 1935) 335. Students paper:The majority of the animal images in the play are Iago's, and all of these are contemptuous or repellent. He refers to a plague of flies, a quarrelsome dog, bird-snaring, leading asses by the nose, a spider catching a fly, beating an offencelessdog, wild cats, goats and monkeys. Through these images the general sense of pain and unpleasantness is increased and kept constantly before us.http://www.dartmouth.edu/~sources/about/what.htmlNot OK:The original text:The main image in Othello is that of animals in action, preying upon one another, mischievous, lascivious, cruel or suffering, and through these, the general sense of pain and unpleasantness is much increased and kept constantly before us. More than half the animal images in the play are Iago's, and all these are contemptuous or repellent: a plague of flies, a quarrelsome dog, the recurrent image of bird-snaring, leading asses by the nose, a spider catching a fly, beating an offencelessdog, wild cats, wolves, goats and monkeys1.1. Caroline F. E. Spurgeon, Shakespeare's Imagery (Cambridge: Cambridge UP, 1935) 335. Students paper:The majority of the animal images in the play are Iago's, and all of these are contemptuous or repellent. He refers to a plague of flies, a quarrelsome dog, bird-snaring, leading asses by the nose, a spider catching a fly, beating an offencelessdog, wild cats, goats and
View Full Document