image University of Washington Computer Science & Engineering
  CSE 527,  Au '09:  Approximate Schedule
  CSE Home   About Us    Search    Contact Info 

Schedule details will evolve as we go; please check back here every week or so to see the latest updates. Items in light font are more tentative than average.

    Due Lecture Topic Reading
Week 1
9/28-10/2		 W   Introduction & Overview Durbin Ch 1-2; Papers Below
Week 2
10/5-10/9		 M   Sequence Alignment, Search & Scoring
W  
Week 3
10/12-10/16		 M  
W  
Week 4
10/19-10/23		 M HW #1 Sequence Motif Modeling & Discovery Durbin 7.1-7.5, Ch 11 (excl Mix. of Dirchlets, Est. Priors in 11.5; skim 11.6); Papers Below
Optional: first 3.5 pages of Durbin 8.6.
W  
Week 5
10/26-10/30		 M  
W  
Week 6
11/2-11/6		 M  
W   HMMs & Gene Finding Durbin Chs 3, 5, Papers Below
Week 7
11/9-11/13		 M  
W Holiday
Week 8
11/16-11/20		 M HW #2 HMMs & Gene Finding
W  
Week 9
11/23-11/27		 M   RNA Structure, Alignment, Search & Discovery Durbin Chs 9-10, Papers Below
W  
Week 10
11/30-12/4		 M  
W  
Week 11
12/7-12/11		 M  
W  

Textbook:

  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 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. I welcome feedback on any of these, and additional suggestions, as to suitability for the course, accessibility, etc.

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.

padlock  Electronic access to journals is generally free from on-campus computers. For off-campus access, follow the "[offcampus]" links or look at the library "proxy server" instructions.  padlock

References -- Introduction & Overview: Read #2; a bit dated, but a good overview. Optional: If you want more biology, former students have recommended Gonick, (also a bit dated, but cheap). Schultz also comes recommended and looks amusing; seems to focus more on genetics. Alberts is a popular undergrad textbook, very comprehensive and very well written. I haven't yet had a chance to look carefully at #3, but first look suggests it's a nice compromise, and also very readable.

  1. Lawrence Hunter, "Molecular Biology for Computer Scientists," Chapter 1 of Artificial Intelligence and Molecular Biology Lawrence Hunter, ed. AAAI press, 1993. (Also here.)
  2. Lawrence Hunter, "The Processes of Life: An Introduction to Molecular Biology," MIT Press, 2009.
  3. Larry Gonick, Mark Wheelis, "The Cartoon Guide to Genetics" (Updated Edition, 1991) ISBN 0062730991, Collins. (Amazon)
  4. Mark Schultz, "The Stuff of Life, a graphic guide to genetics and DNA," Farrar, Straus and Giroux, 2009
  5. Bruce Alberts, Alexander Johnson, Julian Lewis, Martin Raff, Keith Roberts, Peter Walter, "Molecular Biology of the Cell", Fifth Edition, 2007, ISBN 978-0815341055, Garland (Amazon). The 4th edition of this book is available online (although the user interface leaves something to be desired).
  6. Steven L. Salzberg, "A tutorial introduction to computation for biologists," Ch 2 of Computational Methods in Molecular Biology, Salzberg, Searls, and Kasif, eds. Elsevier, 1998

References -- Sequence Alignment, Search & Scoring: Read #8, 9, 12. #13 is an excellent tutorial on scoring, EVD, p- and E-values, etc. #14 goes deeper into the EVD theory for gapped alignments. The Myers review is a bit dated, but still a good overview of algorithms and algorithmic issues.

  1. SR Eddy, "What is dynamic programming?" Nat. Biotechnol., 22, #7 (2004) 909-10. [offcampus]
  2. SR Eddy, "Where did the BLOSUM62 alignment score matrix come from?" Nat. Biotechnol., 22, #8 (2004) 1035-6. [offcampus]
  3. SF Altschul, W Gish, W Miller, EW Myers, DJ Lipman, "Basic local alignment search tool." J. Mol. Biol., 215, #3 (1990) 403-10. [offcampus]
  4. 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]
  5. A Pertsemlidis, JW Fondon, "Having a BLAST with bioinformatics (and avoiding BLASTphemy)." Genome Biol., 2, #10 (2001) REVIEWS2002. [offcampus]
  6. Stephen Altschul, "The Statistics of Sequence Similarity Scores," http://www.ncbi.nlm.nih.gov/blast/tutorial/Altschul-1.html [offcampus]
  7. SF Altschul, R Bundschuh, R Olsen, T Hwa, "The estimation of statistical parameters for local alignment score distributions." Nucleic Acids Res., 29, #2 (2001) 351-61. [offcampus]
  8. Myers, E. (1991) "An overview of sequence comparison algorithms in molecular biology", Tech. Rep. TR-91-29, Dept. of Computer Science, Univ. of Arizona.

References -- Sequence Motif Modeling & Discovery: Read #17, 18, 22, 24, 27. Dempster et al. is the "classic" paper on EM. Eddy is another nice, succinct intro to an important class of methods. Tompa et al. is a comprehensive comparison of several motif finding methods. Blanchette et al. is an important example of use of comparitive genomics for this problem.

  1. 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]
  2. CB Do, S Batzoglou, "What is the expectation maximization algorithm?" Nat. Biotechnol., 26, #8 (2008) 897-9. [offcampus]
  3. GD Stormo, "DNA binding sites: representation and discovery." Bioinformatics, 16, #1 (2000) 16-23. [offcampus]
  4. GD Stormo, GW Hartzell, "Identifying protein-binding sites from unaligned DNA fragments." Proc. Natl. Acad. Sci. U.S.A., 86, #4 (1989) 1183-7. [offcampus]
  5. GZ Hertz, GW Hartzell, GD Stormo, "Identification of consensus patterns in unaligned DNA sequences known to be functionally related." Comput. Appl. Biosci., 6, #2 (1990) 81-92. [offcampus]
  6. GD Stormo, DS Fields, "Specificity, free energy and information content in protein-DNA interactions." Trends Biochem. Sci., 23, #3 (1998) 109-13. [offcampus]
  7. 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. See also http://meme.sdsc.edu/meme/ for related papers and resources.
  8. 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]
  9. 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]
  10. SR Eddy, "What is Bayesian statistics?" Nat. Biotechnol., 22, #9 (2004) 1177-8. [offcampus]
  11. 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]
  12. 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]
  13. 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.
  14. M Blanchette, B Schwikowski, M Tompa, "Algorithms for phylogenetic footprinting." J. Comput. Biol., 9, #2 (2002) 211-23. [offcampus]
  15. M Blanchette, M Tompa, "FootPrinter: A program designed for phylogenetic footprinting." Nucleic Acids Res., 31, #13 (2003) 3840-2. [offcampus]
  16. S Neph, M Tompa, "MicroFootPrinter: a tool for phylogenetic footprinting in prokaryotic genomes." Nucleic Acids Res., 34, #Web Server issue (2006) W366-8. [offcampus]

References -- HMMs & Gene Finding: Read #32, 34. The Rabiner tutorial is a very good intro to HMMs if you want a different perspective from the text. Claverie is a good survey of computational gene finding. Burget and Guigo is a careful comparison of leading programs of its day. Lander et al. and Venter are the landmark initial human genome sequence papers. Klein et al. is an interesting application of HMMs relevant to RNA gene finding, our next topic.

  1. SR Eddy, "What is a hidden Markov model?" Nat. Biotechnol., 22, #10 (2004) 1315-6. [offcampus]
  2. 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.
  3. C Burge, S Karlin, "Prediction of complete gene structures in human genomic DNA." J. Mol. Biol., 268, #1 (1997) 78-94. [offcampus]
  4. M Burset, R Guigó, "Evaluation of gene structure prediction programs." Genomics, 34, #3 (1996) 353-67. [offcampus]
  5. JM Claverie, "Computational methods for the identification of genes in vertebrate genomic sequences." Hum. Mol. Genet., 6, #10 (1997) 1735-44. [offcampus]
  6. An extensive online bibliography
  7. 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]
  8. 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]
  9. 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]
  10. Sharp's Nobel address on discovery of introns.
  11. JP Staley, C Guthrie, "Mechanical devices of the spliceosome: motors, clocks, springs, and things." Cell, 92, #3 (1998) 315-26. [offcampus]

References -- RNA Structure, Alignment, Search & Discovery: Read #47, 52, 54, 56. Optional: Refs 43-46 are good surveys of recent surprising discoveries about the roles of non-coding RNA. Refs 60-62 might give you some picture of one nice biological example and how computational approaches are useful in this arena. Ref #63 and following describe our recent approaches to RNA motif discovery in bacteria and vertebrates.

  1. G Storz, "An expanding universe of noncoding RNAs." Science, 296, #5571 (2002) 1260-3. [offcampus]
  2. SR Eddy, "Computational genomics of noncoding RNA genes." Cell, 109, #2 (2002) 137-40. [offcampus]
  3. A Hüttenhofer, P Schattner, N Polacek, "Non-coding RNAs: hope or hype?" Trends Genet., 21, #5 (2005) 289-97. [offcampus]
  4. G Ruvkun, "The perfect storm of tiny RNAs." Nat. Med., 14, #10 (2008) 1041-5. [offcampus]
  5. SR Eddy, "How do RNA folding algorithms work?" Nat. Biotechnol., 22, #11 (2004) 1457-8. [offcampus]
  6. M Andronescu, A Condon, HH Hoos, DH Mathews, KP Murphy, "Efficient parameter estimation for RNA secondary structure prediction." Bioinformatics, 23, #13 (2007) i19-28. [offcampus]
  7. 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]
  8. RB Lyngsø, M Zuker, CN Pedersen, "Fast evaluation of internal loops in RNA secondary structure prediction." Bioinformatics, 15, #6 (1999) 440-5. [offcampus]
  9. PP Gardner, R Giegerich, "A comprehensive comparison of comparative RNA structure prediction approaches." BMC Bioinformatics, 5, (2004) 140. [offcampus]
  10. SR Eddy, R Durbin, "RNA sequence analysis using covariance models." Nucleic Acids Res., 22, #11 (1994) 2079-88. [offcampus]
  11. SR Eddy, "A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure." BMC Bioinformatics, 3, (2002) 18. [offcampus]
  12. 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]
  13. 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]
  14. 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.
  15. 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]
  16. Z Weinberg, WL Ruzzo, "Sequence-based heuristics for faster annotation of non-coding RNA families." Bioinformatics, 22, #1 (2006) 35-9. [offcampus]
  17. 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]
  18. 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]
  19. 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]
  20. 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]
  21. Z Yao, Z Weinberg, WL Ruzzo, "CMfinder--a covariance model based RNA motif finding algorithm." Bioinformatics, 22, #4 (2006) 445-52. [offcampus]
  22. 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. [offcampus]
  23. 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]
  24. 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]
  25. 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]
  26. Z Weinberg, J Perreault, MM Meyer, RR Breaker, "Exceptional structured noncoding RNAs revealed by bacterial metagenome analysis." Nature, 462, #7273 (2009) 656-9. [offcampus]
  27. 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]

References -- More RNA: Optional: Recent papers mentioned in the last few lectures, mostly related to noncoding RNAs. Refs 63-68 describe CMfinder and applications of it to riboswitch discovery. Refs 70-73 describe RNAz and Evofold and their application to genome-wide discovery in humans, and 69 is our recent paper in this area. Ref 74, 75 describes approaches to identifying evolutionary conservation in noncoding regions.

  1. 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]
  2. 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]
  3. 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. [offcampus]
  4. 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]
  5. G Lunter, CP Ponting, J Hein, "Genome-wide identification of human functional DNA using a neutral indel model." PLoS Comput. Biol., 2, #1 (2006) e5. [offcampus]
  6. J Ponjavic, CP Ponting, G Lunter, "Functionality or transcriptional noise? Evidence for selection within long noncoding RNAs." Genome Res., 17, #5 (2007) 556-65. [offcampus]
  7. T Babak, BJ Blencowe, TR Hughes, "Considerations in the identification of functional RNA structural elements in genomic alignments." BMC Bioinformatics, 8, (2007) 33. [offcampus]
CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX