CSE 427,  Au '18:  Approximate Schedule

CSE Home

About Us

Search

Contact Info

Schedule details will evolve as we go; check back periodically to see the latest updates.

Textbook: None.

Supplementary Text: The following book is an excellent reference for many of the topics we will cover.

1. Richard Durbin, Sean R. Eddy, Anders Krogh and Graeme Mitchison, Biological Sequence Analysis: Probabilistic models of proteins and nucleic acids, Cambridge, 1998.  (Available from U Book Store, Amazon, etc.)  Errata.

References:  As we go forward, I will be updating this list and explicitly designating some of these papers as assigned reading. The rest are optional---good supplementary references, recommended if you want more depth in any of the areas.

Most links below take you to PubMed, the NIH bibliographic database. Usually, but counterintuitively, from a PubMed abstract you click the icon of the publisher (or sometimes the icon saying "UW article online") to get to the actual article.

Journal access: Some of the journals and articles cited below are completely open access, or are freely available via PubMed Central (look for the "Free in PMC" icon).  Electronic access to other cited articles is generally free from on-campus IP addresses.  For off-campus access, follow the "[offcampus]" links or look at the UW library "proxy server" instructions.  Let me know if none of these work for you.

References -- Introduction & Overview: Required: Read #2 and #3. Stephens, et al. (#2) is a nice recent article exploring the "big data" character of modern genomics. Hunter (#3), while a bit dated, is a good overview of molecular biology, at a level that CSE students should find approachable. Optional: Chapter 1 of #1. If you want more biology, #4 is in some ways a book-length expansion of #3; I haven't read it, but the portions I've sampled are good, and not as (potentially) overwhelming as #8. Former students have recommended Gonick, (also a bit dated, but inexpensive). Schultz (#6) also comes recommended, looks amusing, and is also inexpensive; more focused on genetics. Benfey (#7) is newer and targeted towards math/cs/engineering types. (I haven't read this one either; I'd be interested to hear your impressions if you look at it.) Alberts (#8) is a popular undergrad textbook, very comprehensive and very well written. If you locate other, better background references, please email a link to me and to the class list.

2. ZD Stephens, SY Lee, F Faghri, RH Campbell, C Zhai, MJ Efron, R Iyer, MC Schatz, S Sinha, GE Robinson, "Big Data: Astronomical or Genomical?" PLoS Biol., 13, #7 (2015) e1002195.
3. Lawrence Hunter, "Molecular Biology for Computer Scientists," Chapter 1 of Artificial Intelligence and Molecular Biology Lawrence Hunter, ed. AAAI press, 1993. (Also here.)
4. Lawrence Hunter, The Processes of Life: An Introduction to Molecular Biology, The MIT Press, 2009, ISBN 978-0262013055, 320 pages. (Amazon)
5. Larry Gonick, Mark Wheelis, "The Cartoon Guide to Genetics" (Updated Edition, 1991) ISBN 0062730991, Collins. (Amazon)
6. Mark Schultz, "The Stuff of Life, a graphic guide to genetics and DNA," Farrar, Straus and Giroux, 2009 (Amazon)
7. Philip N. Benfey, Quickstart Molecular Biology: An Introductory Course for Mathematicians, Physicists, and Engineers, Cold Spring Harbor Press, 2014, (CSH Press)
8. Bruce Alberts, Alexander Johnson, Julian Lewis, Martin Raff, Keith Roberts, Peter Walter, "Molecular Biology of the Cell", Fifth Edition, 2007, ISBN 978-0815341055, Garland, 1392 pages. (Amazon) The 4th edition of this book is available online (although the user interface leaves something to be desired; in particular, you must use the "search" feature on that page instead of browsing...).

References -- Sequence Alignment, Search & Scoring: Required: Read #12, 13. Optional: Chapter 2 of #1. The original BLAST paper is #9; #11 describes important extensions to it. The Myers review is a bit dated, but still a good overview of algorithms and algorithmic issues. #14 discusses practical pitfalls. #16 gives a much deeper look at the theory underlying permutation p-values.

9. SF Altschul, W Gish, W Miller, EW Myers, DJ Lipman, "Basic local alignment search tool." J. Mol. Biol., 215, #3 (1990) 403-10. [offcampus] (Available here or here.)
10. Myers, E. (1991) "An overview of sequence comparison algorithms in molecular biology", Tech. Rep. TR-91-29, Dept. of Computer Science, Univ. of Arizona.
11. SF Altschul, TL Madden, AA Schäffer, J Zhang, Z Zhang, W Miller, DJ Lipman, "Gapped BLAST and PSI-BLAST: a new generation of protein database search programs." Nucleic Acids Res., 25, #17 (1997) 3389-402. [offcampus]
12. SR Eddy, "What is dynamic programming?" Nat. Biotechnol., 22, #7 (2004) 909-10. [offcampus]
13. SR Eddy, "Where did the BLOSUM62 alignment score matrix come from?" Nat. Biotechnol., 22, #8 (2004) 1035-6. [offcampus]
14. A Pertsemlidis, JW Fondon, "Having a BLAST with bioinformatics (and avoiding BLASTphemy)." Genome Biol., 2, #10 (2001) REVIEWS2002. [offcampus]
15. Lobo, I. (2008) Basic Local Alignment Search Tool (BLAST). Nature Education 1(1):215
16. B Phipson, GK Smyth, "Permutation P-values should never be zero: calculating exact P-values when permutations are randomly drawn." Stat Appl Genet Mol Biol, 9, (2010) Article39. [offcampus]

References -- Sequence Motif Modeling & Discovery: MLE & the EM Algorithm: Required: Read #17. Dempster et al. is the "classic" paper on EM. #19 is a very readable introduction to the Gaussian model-based clustering method outlined in lecture (and to BIC scores for model selection, which I very briefly mengtioned in lecture and sometimes use in the homework), and #20 gives a biological application of these ideas. The others suggest additional resources on MLE and EM.

17. CB Do, S Batzoglou, "What is the expectation maximization algorithm?" Nat. Biotechnol., 26, #8 (2008) 897-9. [offcampus]
18. AP Dempster, NM Laird, DB Rubin, "Maximum Likelihood from Incomplete Data via the EM Algorithm," Journal of the Royal Statistical Society. Series B (Methodological), Vol. 39, No. 1. (1977), pp. 1-38. Available here. [offcampus]
19. Fraley, C, and A E Raftery. 1998. "How Many Clusters? Which Clustering Method? Answers via Model-Based Cluster Analysis." The Computer Journal 41 (8): 578-588. [offcampus]
20. KY Yeung, C Fraley, A Murua, AE Raftery, WL Ruzzo, "Model-based clustering and data transformations for gene expression data." Bioinformatics, 17, #10 (2001) 977-87. [offcampus]
21. Wikipedia covers many of the basic statistical topics. Its coverage can be uneven and/or too advanced, but much is useful. E.g., here are some specifics on likelihood:
    • Likelihood Function (through 2.1).
    • Likelihood-ratio test ("Background" and "Simple-versus-simple hypotheses"),
22. Wolfram's MathWorld, (by E.W. Weisstein), also covers much of this ground, but again not always at the right level for beginners. One specific topic that might be of interest:
    • "Maximum Likelihood."
23. More detail on EM and model-based clustering:
    • Notes from another course.
    • Dinov, Ivo D. (2008). Expectation Maximization and Mixture Modeling Tutorial. UC Los Angeles: Statistics Online Computational Resource. Retrieved from: http://escholarship.org/uc/item/1rb70972
    [offcampus]
    • A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models, J.A. Bilmes, 1998.

References -- Sequence Motif Modeling & Discovery: MEME & Gibbs Sampling: Required: Read #24, 25, 27. Stormo is a nice survey from a slightly more biological perspective. Tompa et al. is a comprehensive comparison of several motif finding methods. Blanchette et al. is an important example of use of comparative genomics for this problem. #33 is highly recommended: another nice, succinct intro to an important class of methods that we will use, but I didn't directly lecture on it.

24. GD Stormo, "DNA binding sites: representation and discovery." Bioinformatics, 16, #1 (2000) 16-23. [offcampus]
25. TL Bailey, C Elkan, "Fitting a mixture model by expectation maximization to discover motifs in biopolymers." Proc Int Conf Intell Syst Mol Biol, 2, (1994) 28-36. [offcampus] Available here: (.ps) (.pdf) See also http://meme.sdsc.edu/meme/ for related papers and resources.
26. TL Bailey, C Elkan, "The value of prior knowledge in discovering motifs with MEME." Proc Int Conf Intell Syst Mol Biol, 3, (1995) 21-9. [offcampus]
27. CE Lawrence, SF Altschul, MS Boguski, JS Liu, AF Neuwald, JC Wootton, "Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment." Science, 262, #5131 (1993) 208-14. [offcampus] Available here. [offcampus]
28. FP Roth, JD Hughes, PW Estep, GM Church, "Finding DNA regulatory motifs within unaligned noncoding sequences clustered by whole-genome mRNA quantitation." Nat. Biotechnol., 16, #10 (1998) 939-45. [offcampus]
29. M Tompa, N Li, TL Bailey, GM Church, B De Moor, E Eskin, AV Favorov, MC Frith, Y Fu, WJ Kent, et 15 al., "Assessing computational tools for the discovery of transcription factor binding sites." Nat. Biotechnol., 23, #1 (2005) 137-44. [offcampus]
30. Emily Rocke and Martin Tompa An Algorithm for Finding Novel Gapped Motifs in DNA Sequences RECOMB98: Proceedings of the Second Annual International Conference on Computational Molecular Biology, New York, NY, March 1998, 228-233.
31. M Blanchette, B Schwikowski, M Tompa, "Algorithms for phylogenetic footprinting." J. Comput. Biol., 9, #2 (2002) 211-23. [offcampus]
32. M Blanchette, M Tompa, "FootPrinter: A program designed for phylogenetic footprinting." Nucleic Acids Res., 31, #13 (2003) 3840-2. [offcampus]
33. SR Eddy, "What is Bayesian statistics?" Nat. Biotechnol., 22, #9 (2004) 1177-8. [offcampus]

References -- HMMs & Gene Finding: Required: Read #34 and Chapter 3 of #1. (The later is available HERE). #35 is also a very good tutorial/intro to HMMs from a different perspective (speech analysis). #41 is an interesting application of HMMs relevant to RNA gene finding, a later topic.

34. SR Eddy, "What is a hidden Markov model?" Nat. Biotechnol., 22, #10 (2004) 1315-6. [offcampus]
35. LR Rabiner, "A Tutorial on Hidden Markov Models and Selected Application in Speech Recognition," Proceedings of the IEEE, v 77 #2,Feb 1989, 257-286.
36. C Burge, S Karlin, "Prediction of complete gene structures in human genomic DNA." J. Mol. Biol., 268, #1 (1997) 78-94. [offcampus]
37. M Burset, R Guigó, "Evaluation of gene structure prediction programs." Genomics, 34, #3 (1996) 353-67. [offcampus]
38. JM Claverie, "Computational methods for the identification of genes in vertebrate genomic sequences." Hum. Mol. Genet., 6, #10 (1997) 1735-44. [offcampus]
39. ES Lander, LM Linton, B Birren, C Nusbaum, MC Zody, J Baldwin, K Devon, K Dewar, M Doyle, W FitzHugh, et 247 al., "Initial sequencing and analysis of the human genome." Nature, 409, #6822 (2001) 860-921. [offcampus]
40. JC Venter, MD Adams, EW Myers, PW Li, RJ Mural, GG Sutton, HO Smith, M Yandell, CA Evans, RA Holt, et 264 al., "The sequence of the human genome." Science, 291, #5507 (2001) 1304-51. [offcampus]
41. RJ Klein, Z Misulovin, SR Eddy, "Noncoding RNA genes identified in AT-rich hyperthermophiles." Proc. Natl. Acad. Sci. U.S.A., 99, #11 (2002) 7542-7. [offcampus]
42. Phillip A. Sharp, Split Genes and RNA Splicing, Nobel Lecture, December 8, 1993, http://nobelprize.org/nobel_prizes/medicine/laureates/1993/sharp-lecture.pdf [offcampus]
43. JP Staley, C Guthrie, "Mechanical devices of the spliceosome: motors, clocks, springs, and things." Cell, 92, #3 (1998) 315-26. [offcampus]
44. DR Edgell, VR Chalamcharla, M Belfort, "Learning to live together: mutualism between self-splicing introns and their hosts." BMC Biol., 9, (2011) 22.
45. Cute animation of the splicing process. Not as detailed as the "Motors" paper above, but you might like it: http://vcell.ndsu.nodak.edu/animations/mrnasplicing/movie.htm

References -- RNA & RNA structure: Required: Read #51. Optional: these papers survey recent surprising discoveries about the roles of non-coding RNA, and some recent computational techniques for RNA analysis. The papers on 6S might give you some picture of one nice biological example and how computational approaches are useful in this arena. The last few papers (76-81) focus on discovery of ncRNAs in vertebrates.

46. G Storz, "An expanding universe of noncoding RNAs." Science, 296, #5571 (2002) 1260-3. [offcampus]
47. SR Eddy, "Computational genomics of noncoding RNA genes." Cell, 109, #2 (2002) 137-40. [offcampus]
48. A Hüttenhofer, P Schattner, N Polacek, "Non-coding RNAs: hope or hype?" Trends Genet., 21, #5 (2005) 289-97. [offcampus]
49. G Ruvkun, "The perfect storm of tiny RNAs." Nat. Med., 14, #10 (2008) 1041-5. [offcampus]
50. J Gorodkin, IL Hofacker, E Torarinsson, Z Yao, JH Havgaard, WL Ruzzo, "De novo prediction of structured RNAs from genomic sequences." Trends Biotechnol., 28, #1 (2010) 9-19. [offcampus]
51. SR Eddy, "How do RNA folding algorithms work?" Nat. Biotechnol., 22, #11 (2004) 1457-8. [offcampus]
52. JS McCaskill, "The equilibrium partition function and base pair binding probabilities for RNA secondary structure." Biopolymers, 29, #6-7 (1990 May-Jun) 1105-19. [offcampus]
53. RB Lyngsø, M Zuker, CN Pedersen, "Fast evaluation of internal loops in RNA secondary structure prediction." Bioinformatics, 15, #6 (1999) 440-5. [offcampus]
54. PP Gardner, R Giegerich, "A comprehensive comparison of comparative RNA structure prediction approaches." BMC Bioinformatics, 5, (2004) 140.
55. Y Sakakibara, M Brown, R Hughey, IS Mian, K Sjölander, RC Underwood, D Haussler, "Stochastic context-free grammars for tRNA modeling." Nucleic Acids Res., 22, #23 (1994) 5112-20. [offcampus]
56. SR Eddy, R Durbin, "RNA sequence analysis using covariance models." Nucleic Acids Res., 22, #11 (1994) 2079-88. [offcampus]
57. SR Eddy, "A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure." BMC Bioinformatics, 3, (2002) 18.
58. S Griffiths-Jones, A Bateman, M Marshall, A Khanna, SR Eddy, "Rfam: an RNA family database." Nucleic Acids Res., 31, #1 (2003) 439-41. [offcampus]
59. S Griffiths-Jones, S Moxon, M Marshall, A Khanna, SR Eddy, A Bateman, "Rfam: annotating non-coding RNAs in complete genomes." Nucleic Acids Res., 33, #Database issue (2005) D121-4. [offcampus]
60. B Knudsen, J Hein, "RNA secondary structure prediction using stochastic context-free grammars and evolutionary history." Bioinformatics, 15, #6 (1999) 446-54. [offcampus]
61. B Knudsen, J Hein, "Pfold: RNA secondary structure prediction using stochastic context-free grammars." Nucleic Acids Res., 31, #13 (2003) 3423-8. [offcampus]
62. Z Weinberg, WL Ruzzo, "Faster Genome Annotation of Non-coding RNA Families Without Loss of Accuracy." Eighth Annual International Conference on Research in Computational Molecular Biology (RECOMB 2004) , pp 243-251, March 2004, San Diego, CA. Preprint.
63. Z Weinberg, WL Ruzzo, "Exploiting conserved structure for faster annotation of non-coding RNAs without loss of accuracy." Bioinformatics, 20 Suppl 1, (2004) i334-41. [offcampus]
64. Z Weinberg, WL Ruzzo, "Sequence-based heuristics for faster annotation of non-coding RNA families." Bioinformatics, 22, #1 (2006) 35-9. [offcampus]
65. M Mandal, M Lee, JE Barrick, Z Weinberg, GM Emilsson, WL Ruzzo, RR Breaker, "A glycine-dependent riboswitch that uses cooperative binding to control gene expression." Science, 306, #5694 (2004) 275-9. [offcampus]
66. JE Barrick, N Sudarsan, Z Weinberg, WL Ruzzo, RR Breaker, "6S RNA is a widespread regulator of eubacterial RNA polymerase that resembles an open promoter." RNA, 11, #5 (2005) 774-84. [offcampus]
67. AE Trotochaud, KM Wassarman, "A highly conserved 6S RNA structure is required for regulation of transcription." Nat. Struct. Mol. Biol., 12, #4 (2005) 313-9. [offcampus]
68. DK Willkomm, J Minnerup, A Hüttenhofer, RK Hartmann, "Experimental RNomics in Aquifex aeolicus: identification of small non-coding RNAs and the putative 6S RNA homolog." Nucleic Acids Res., 33, #6 (2005) 1949-60. [offcampus]
69. T Babak, BJ Blencowe, TR Hughes, "Considerations in the identification of functional RNA structural elements in genomic alignments." BMC Bioinformatics, 8, (2007) 33.
70. Z Yao, Z Weinberg, WL Ruzzo, "CMfinder--a covariance model based RNA motif finding algorithm." Bioinformatics, 22, #4 (2006) 445-52. [offcampus]
71. Z Yao, J Barrick, Z Weinberg, S Neph, R Breaker, M Tompa, WL Ruzzo, "A computational pipeline for high- throughput discovery of cis-regulatory noncoding RNA in prokaryotes." PLoS Comput. Biol., 3, #7 (2007) e126.
72. Z Weinberg, JE Barrick, Z Yao, A Roth, JN Kim, J Gore, JX Wang, ER Lee, KF Block, N Sudarsan, et 4 al., "Identification of 22 candidate structured RNAs in bacteria using the CMfinder comparative genomics pipeline." Nucleic Acids Res., 35, #14 (2007) 4809-19. [offcampus]
73. EE Regulski, RH Moy, Z Weinberg, JE Barrick, Z Yao, WL Ruzzo, RR Breaker, "A widespread riboswitch candidate that controls bacterial genes involved in molybdenum cofactor and tungsten cofactor metabolism." Mol. Microbiol., 68, #4 (2008) 918-32. [offcampus]
74. Z Weinberg, EE Regulski, MC Hammond, JE Barrick, Z Yao, WL Ruzzo, RR Breaker, "The aptamer core of SAM-IV riboswitches mimics the ligand-binding site of SAM-I riboswitches." RNA, 14, #5 (2008) 822-8. [offcampus]
75. J Gorodkin, IL Hofacker, E Torarinsson, Z Yao, JH Havgaard, WL Ruzzo, "De novo prediction of structured RNAs from genomic sequences." Trends Biotechnol., 28, #1 (2010) 9-19. [offcampus]
76. S Washietl, IL Hofacker, PF Stadler, "Fast and reliable prediction of noncoding RNAs." Proc. Natl. Acad. Sci. U.S.A., 102, #7 (2005) 2454-9. [offcampus]
77. S Washietl, IL Hofacker, M Lukasser, A Hüttenhofer, PF Stadler, "Mapping of conserved RNA secondary structures predicts thousands of functional noncoding RNAs in the human genome." Nat. Biotechnol., 23, #11 (2005) 1383-90. [offcampus]
78. JS Pedersen, G Bejerano, A Siepel, K Rosenbloom, K Lindblad-Toh, ES Lander, J Kent, W Miller, D Haussler, "Identification and classification of conserved RNA secondary structures in the human genome." PLoS Comput. Biol., 2, #4 (2006) e33.
79. S Washietl, JS Pedersen, JO Korbel, C Stocsits, AR Gruber, J Hackermüller, J Hertel, M Lindemeyer, K Reiche, A Tanzer, et 14 al., "Structured RNAs in the ENCODE selected regions of the human genome." Genome Res., 17, #6 (2007) 852-64. [offcampus]
80. E Torarinsson, Z Yao, ED Wiklund, JB Bramsen, C Hansen, J Kjems, N Tommerup, WL Ruzzo, J Gorodkin, "Comparative genomics beyond sequence-based alignments: RNA structures in the ENCODE regions." Genome Res., 18, #2 (2008) 242-51. [offcampus]
81. SE Seemann, AH Mirza, C Hansen, CH Bang-Berthelsen, C Garde, M Christensen-Dalsgaard, E Torarinsson, Z Yao, CT Workman, F Pociot, H Nielsen, N Tommerup, WL Ruzzo, J Gorodkin, "The identification and functional annotation of RNA structures conserved in vertebrates." Genome Res., 27, #8 (2017) 1371-1383. [offcampus]

References -- Special Topic & Wrapup: The diatom example I talked about comes from 82.

82. JA Koester, CT Berthiaume, N Hiranuma, MS Parker, V Iverson, R Morales, WL Ruzzo, EV Armbrust, "Sexual ancestors generated an obligate asexual and globally dispersed clone within the model diatom species Thalassiosira pseudonana." Sci Rep, 8, #1 (2018) 10492. [offcampus]

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX