Biostatistics & Medical Informatics 776
Computer Sciences 776
Advanced Bioinformatics (Spring 2009)

General Course Information Syllabus, Readings, Lecture Notes Announcements, Homework, Project

Syllabus, Readings and Lecture Notes Motif and CRM Modeling topics: motif modeling, MEME, Gibbs sampling, Dirichlet priors, cis-regulatory modules, HMM structure search, mutual information required reading T. Bailey and C. Elkan. The value of prior knowledge in discovering motifs with MEME. In Proceedings of the 3rd International Conference on Intelligent Systems for Molecular Biology, pp. 21-29, 1995. C. Lawrence, S. Altschul, M. Boguski, J. Liu, A. Neuwald, and J. Wootton. Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment. Science 262:208-214, 1993. K. Noto and M. Craven. Learning probabilistic models of cis-regulatory modules that represent logical and spatial aspects. Bioinformatics 23(2):e156-e162, 2007. O. Elemento, N. Slonim and S. Tavazoie. A universal framework for regulatory element discovery across all genomes and data types. Molecular Cell 28(2):337-350, 2007. optional reading M. Tompa et al. Assessing computational tools for the discovery of transcription factor binding sites. Nature Biotechnology 23(1):137-144, 2005. lecture notes Course Overview (1/20) Learning Sequence Motif Models (1/22, 1/27, 1/29) Learning Models of cis-Regulatory Modules (2/3, 2/5, 2/9) (updated 2/5) Gene Finding topics: gene recognition, Genscan, Twinscan, SLAM, semi-Markov models, maximal dependence decomposition, interpolated Markov models, back-off models, pairwise HMMs required reading S. Salzberg, A. Delcher, S. Kasif, and O. White. Microbial gene identification using interpolated Markov models. Nucleic Acids Research 26(2):544-548, 1998. Section 3.4 in Durbin et al. C. Burge and S. Karlin. Prediction of complete gene structures in human genomic DNA. Journal of Molecular Biology 268(1):78-94. I. Korf, P. Flicek, D. Duan, and M. Brent. Integrating genomic homology into gene structure prediction. Bioinformatics 17(Suppl. 1):S140-S148, 2001. L. Pachter, M. Alexandersson and S. Cawley. Applications of generalized pair hidden Markov models to alignment and gene finding problems. Proceedings of the Fifth Annual International Conference on Computational Biology (RECOMB), 241-248, 2001. lecture notes Interpolated Markov Models for Gene Finding (2/17) Eukaryotic Gene Finding: The GENSCAN System (2/19, 2/24) (updated 2/24) Comparative Gene Finding (2/24, 2/26, 3/3) (updated 3/3) Advanced Topics in Sequence Alignment topics: large-scale alignment, whole-genome alignment, parametric alignment, suffix trees, locality sensitive hashing, k-mer tries, sparse dynamic programming, MUMmer, LAGAN/MLAGAN, Mauve required reading A. Delcher, S. Kasif, R. Fleischmann, J. Peterson, O. White and S. Salzberg. Alignment of Whole Genomes. Nucleic Acids Research 27(11):2369-2376, 1999. M. Brudno, C. Do, G. Cooper, M. Kim, E. Davydov, NISC Comparative Sequencing Program, E. Green, A. Sidow, and S. Batzoglou. LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA. Genome Research 13:721-731, 2003. A. Darling, B. Mau, F. Blattner and N. Perna. Mauve: Multiple Alignment of Conserved Genomic Sequence with Rearrangements. Genome Research 14:1394-1403, 2004. optional reading E. Ukkonen. On-line Construction of Suffix Trees Algorithmica 14(3):249-260, 1995. N. Bray, I. Dubchak and L. Pachter. AVID: A Global Alignment Program. Genome Research 13:97-102, 2003. Chapter 3 of C. Dewey. Whole-genome alignments and polytopes for comparative genomics. PhD thesis. University of California, Berkeley, 2006. lecture notes Pattern Matching with Suffix Trees (3/3, 3/10) Aligning Long Sequences (3/5, 3/10) Multiple Whole-Genome Alignment (3/12, 3/24) RNA Analysis topics: predicting RNA secondary structure, Nussinov/energy-minimization algorithms, stochastic context free grammars, Inside/Inside-Outside/CYK algorithms, searching sequences for a given RNA secondary structure, RSEARCH, RNA gene recognition via comparative sequence analysis, microRNA gene/target prediction required reading Chapter 9 in Durbin et al. Sections 10.1, 10.2 in Durbin et al. R. Klein and S. Eddy. RSEARCH: Finding homologs of single structured RNA sequences. BMC Bioinformatics 4(44), 2003. E. Rivas and S. Eddy. Noncoding RNA gene detection using comparative sequence analysis. BMC Bioinformatics 2(8), 2001. optional reading Y. Sakakibara, M. Brown, R. Hughey, I. Mian, K. Sjolander, R. Underwood and D. Haussler. Stochastic context-free grammars for tRNA modeling. Nucleic Acids Research 22(23):5112-5120, 1994. lecture notes RNA Secondary Structure Prediction (3/24) Stochastic Context Free Grammars for RNA Structure Modeling (3/31, 4/2) Applications of Lightweight Stochastic Context Free Grammars to RNA Analysis (4/7, 4/9) Representation, Learning and Inference in Models of Cellular Networks topics: Bayesian networks, module networks, experiment design, abduction, flux balance analysis required reading E. Segal, M. Shapira, A. Regev, D. Pe'er, D. Botstein, D. Koller and N. Friedman. Module networks: identifying regulatory modules and their condition-specific regulators from gene expression data. Nature Genetics 34(2):166-176, 2003. R. King, K. Whelan, F. Jones, P. Reiser, C. Bryant, S. Muggleton, D. Kell, and S. Oliver. Functional genomic hypothesis generation and experimentation by a robot scientist. Nature 427:247-252, 2004. R. King, J. Rowland, S. Oliver, M. Young, W. Aubrey, E. Byrne, M. Liakata, M. Markham, P. Pir, L. Soldatova, A. Sparkes, K. Whelan, A. Clare. The Automation of Science. Science 324:85-89, 2009. N. Price, J. Reed, and B. Palsson. Genome-scale models of microbial cells: evaluating the consequences of constraints. Nature Reviews Microbiology 2:886-897, 2004. optional reading I. Nachman, A. Regev, and N. Friedman. Inferring quantitative models of regulatory networks from expression data. Bioinformatics 20(Suppl. 1):i248-i256, 2004. P. Reiser, R. King, D. Kell, S. Muggleton, and S. Oliver. Developing a logical model of yeast metabolism. Electronic Transactions in Artificial Intelligence 5:233-244, 2001. lecture notes Models of Cellular Networks (4/14) Module Networks (4/14, 16) (updated 4/21) Refining Metabolic Network Models in the Robot Scientist Project (4/16, 4/21) Inference in Metabolic Network Models using Flux Balance Analysis (4/23) Biomedical Text Mining topics: named entity recognition, relation extraction, topic modeling required reading M. Craven and H. Shatkay. Chapter 4: Information Extraction. From Biomedical Text Mining. MIT Press, forthcoming. recommended reading D. Swanson and N. Smalheiser. An interactive system for finding complementary literatures: a stimulus to scientific discovery. Artificial Intelligence 91(2):183-203, 1997. H. Shatkay, S. Edwards, W.J. Wilbur and M. Boguski. Genes, themes and microarrays. Proceedings of the International Conference on Intelligent Systems for Molecular Biology, pp. 317-328, 2000. lecture notes Biomedical Text Analysis (4/28) Information Extraction from Biomedical Text (4/30) Association Studies topics: regression approaches, haplotype reconstruction (phasing) required reading lecture notes