Schedule details will evolve as we go; please check
back here every week or so to see the latest updates.
|
|
Due |
Lecture Topic |
Reading |
Week 1 1/7-1/11 |
Tu |
|
Introduction & Overview |
Papers Below |
Th |
|
Week 2 1/14-1/18 |
Tu |
|
Gene Finding |
Papers Below |
Th |
|
Week 3 1/21-1/25 |
Tu |
|
Markov and Hidden Markov Models |
Papers Below |
Th |
|
Week 4 1/28-2/1 |
Tu |
|
Th |
|
Sequence Alignment, Search & Scoring |
Papers Below |
Week 5 2/4-2/8 |
Tu |
HW #1 |
Th |
|
Week 6 2/11-2/15 |
Tu |
|
Th |
|
Week 7 2/18-2/22 |
Tu |
HW #2 |
RNA Structure, Alignment, & Search |
Papers Below |
Th |
|
Week 8 2/25-2/29 |
Tu |
|
Th |
|
Week 9 3/3-3/7 |
Tu |
HW #3 |
Th |
|
Week 10 3/10-3/14 |
Tu |
|
Th |
|
References -- Introduction & Overview:
Read:
#1 (a short, readable intro to the basics); and
#2 (slightly dated, but more comprehensive).
Optional: If you want more biology, former students have
recommended Gonick, (also a bit dated, but cheap). Alberts is a
popular undergrad textbook, very comprehensive and very well
written.
- Tompa's "Basics of Mol. Bio." (Class notes from last year.)
- Lawrence Hunter, "Molecular Biology for Computer
Scientists," Chapter 1 of Artificial
Intelligence and Molecular Biology Lawrence Hunter,
ed. AAAI press, 1993. (Also here.)
- Larry Gonick, Mark Wheelis, "The Cartoon Guide to Genetics"
(Updated Edition, 1991) ISBN 0062730991, Collins. (Amazon)
- Bruce Alberts, Alexander Johnson, Julian Lewis, Martin Raff,
Keith Roberts, Peter Walter, "Molecular Biology of the Cell",
Fourth Edition, 2002, ISBN 0815332181, Garland (Amazon.
This book is also available online, although the web version is somewhat hard to navigate.)
References -- Gene Finding:
TBA
References -- Markov and Hidden Markov Models:
Read #5 and Chapter 4 of #6. (The later is
available HERE). The Rabiner
tutorial is also a very good intro to HMMs if you want a different
perspective from the text.
- SR Eddy, "What is a hidden Markov model?" Nat. Biotechnol., 22, #10 (2004) 1315-6.
[offcampus]
- Richard Durbin, Sean R. Eddy, Anders Krogh and Graeme Mitchison,
Biological Sequence Analysis: Probabilistic models of proteins and nucleic acids,
Cambridge, 1998.
(
Amazon)
Errata.
- 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. here.
References -- Sequence Alignment, Search & Scoring:
Read #8, 9, 11. The Myers review is a bit dated, but still a
good overview of algorithms and algorithmic issues.
- SR Eddy, "What is dynamic programming?" Nat. Biotechnol., 22, #7 (2004) 909-10.
[offcampus]
- SR Eddy, "Where did the BLOSUM62 alignment score matrix come from?" Nat. Biotechnol., 22, #8 (2004) 1035-6.
[offcampus]
- A Pertsemlidis, JW Fondon, "Having a BLAST with bioinformatics (and avoiding BLASTphemy)." Genome Biol., 2, #10 (2001) REVIEWS2002.
[offcampus]
- SF Altschul, W Gish, W Miller, EW Myers, DJ Lipman, "Basic local alignment search tool." J. Mol. Biol., 215, #3 (1990) 403-10.
[offcampus]
- 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]
- Stephen Altschul, "The Statistics of Sequence Similarity Scores,"
http://www.ncbi.nlm.nih.gov/blast/tutorial/Altschul-1.html [offcampus]
- Myers, E. (1991) "An overview of sequence comparison
algorithms in molecular biology",
Tech. Rep. TR-91-29, Dept. of Computer Science, Univ. of
Arizona.
- Tompa's
notes on Multiple Sequence Alignment
References -- RNA Structure, Alignment, & Search:
Read #19, 23, 25. Optional: Refs 16-18 are good surveys of
recent surprising discoveries about the roles of non-coding RNA.
Refs 34-36 might give you some picture of one nice biological
example and how computational approaches are useful in this
arena.
- G Storz, "An expanding universe of noncoding RNAs." Science, 296, #5571 (2002) 1260-3.
[offcampus]
- SR Eddy, "Computational genomics of noncoding RNA genes." Cell, 109, #2 (2002) 137-40.
[offcampus]
- A Hüttenhofer, P Schattner, N Polacek, "Non-coding RNAs: hope or hype?" Trends Genet., 21, #5 (2005) 289-97.
[offcampus]
- SR Eddy, "How do RNA folding algorithms work?" Nat. Biotechnol., 22, #11 (2004) 1457-8.
[offcampus]
- 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]
- RB Lyngsø, M Zuker, CN Pedersen, "Fast evaluation of internal loops in RNA secondary structure prediction." Bioinformatics, 15, #6 (1999) 440-5.
[offcampus]
- PP Gardner, R Giegerich, "A comprehensive comparison of comparative RNA structure prediction approaches." BMC Bioinformatics, 5, (2004) 140.
[offcampus]
- SR Eddy, R Durbin, "RNA sequence analysis using covariance models." Nucleic Acids Res., 22, #11 (1994) 2079-88.
[offcampus]
- 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]
- 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]
- 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]
- B Knudsen, J Hein, "RNA secondary structure prediction using stochastic context-free grammars and evolutionary history." Bioinformatics, 15, #6 (1999) 446-54.
[offcampus]
- B Knudsen, J Hein, "Pfold: RNA secondary structure prediction using stochastic context-free grammars." Nucleic Acids Res., 31, #13 (2003) 3423-8.
[offcampus]
- 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.
- 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]
- Z Weinberg, WL Ruzzo, "Sequence-based heuristics for faster annotation of non-coding RNA families." Bioinformatics, 22, #1 (2006) 35-9.
[offcampus]
- 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]
- 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]
- 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]
- 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]
- T Babak, BJ Blencowe, TR Hughes, "Considerations in the identification of functional RNA structural elements in genomic alignments." BMC Bioinformatics, 8, (2007) 33.
[offcampus]
References -- :
Optional: Recent papers mentioned in the last few
lectures, mostly related to noncoding RNAs. Refs 37-39
describe CMfinder and our applications of it to riboswitch
discovery. Refs 40-43 describe RNAz and Evofold and their
application to genome-wide discovery in humans, and 44 is
our recent paper in this area. Ref 45-46 describes approaches
to identifying evolutionary conservation in noncoding regions.
- Z Yao, Z Weinberg, WL Ruzzo, "CMfinder--a covariance model based RNA motif finding algorithm." Bioinformatics, 22, #4 (2006) 445-52.
[offcampus]
- 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]
- Z Weinberg, JE Barrick, Z Yao, A Roth, JN Kim, J Gore, JX Wang, ER Lee, KF Block, N Sudarsan, S Neph, M Tompa, WL Ruzzo, RR Breaker, "Identification of 22 candidate structured RNAs in bacteria using the CMfinder comparative genomics pipeline." Nucleic Acids Res., 35, #14 (2007) 4809-19.
[offcampus]
- 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]
- 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]
- 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]
- S Washietl, JS Pedersen, JO Korbel, C Stocsits, AR Gruber, J Hackermüller, J Hertel, M Lindemeyer, K Reiche, A Tanzer, C Ucla, C Wyss, SE Antonarakis, F Denoeud, J Lagarde, J Drenkow, P Kapranov, TR Gingeras, R Guigó, M Snyder, MB Gerstein, A Reymond, IL Hofacker, PF Stadler, "Structured RNAs in the ENCODE selected regions of the human genome." Genome Res., 17, #6 (2007) 852-64.
[offcampus]
- Torarinsson, Yao, Wiklund, Bramsen, Hansen, Kjems, Tommerup,
Ruzzo and Gorodkin. Comparative genomics beyond sequence based
alignments: RNA structures in the ENCODE regions. Genome Research,
To Appear.
- 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]
- 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]
|
|
Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
|