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

General Course Information What's New Syllabus, Readings, Lecture Notes Schedule Homework, Project, Exam Info

Syllabus, Readings and Lecture Notes Course Overview lecture notes Course Overview (1/18) Motif and cis-Regulatory Module (CRM) Modeling topics: learning motif models, learning models of cis-regulatory modules, Gibbs sampling, Dirichlet priors, parameter tying, heuristic search, HMM structure search, sequence entropy and mutual information, duration modeling, semi-Markov models 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 Learning Sequence Motif Models using EM (1/20) (updated 1/27) Learning Sequence Motif Models using Gibbs Sampling (1/25, 1/27) (updated 1/27) Inferring Probabilistic Models of cis-Regulatory Modules (1/27, 2/1) Inferring Models of cis-Regulatory Modules using Information Theory (2/3, 2/8) Gene Finding topics: the gene finding task, maximal dependence decomposition, interpolated Markov models, back-off models, pairwise HMMs, Genscan, Twinscan, SLAM 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, 1997. Sections 4.1, 4.2 in Durbin et al. 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. optional reading I. Korf, P. Flicek, D. Duan, and M. Brent. Integrating genomic homology into gene structure prediction. Bioinformatics 17(Suppl. 1):S140-S148, 2001. lecture notes Interpolated Markov Models for Gene Finding (2/8, 2/15) Eukaryotic Gene Finding: The GENSCAN System (2/15, 2/17) Comparative Gene Finding (2/17, 2/22) Large-Scale and Whole-Genome Sequence Alignment topics: large-scale alignment, whole-genome alignment, parametric alignment, suffix trees, locality sensitive hashing, k-mer tries, sparse dynamic programming, longest increasing subsequence problem, Markov random fields, MUMmer, LAGAN/MLAGAN, Mauve, Mercator 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. 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. A. Darling, B. Mau, F. Blattner and N. Perna. Mauve: Multiple Alignment of Conserved Genomic Sequence with Rearrangements. Genome Research 14:1394-1403, 2004. Chapter 3 of C. Dewey. Whole-genome alignments and polytopes for comparative genomics. PhD thesis. University of California, Berkeley, 2006. lecture notes Alignment of Long Sequences (2/24, 3/1) Serafim Batzoglou's PowerPoint slides on chaining local alignments (3/1) Multiple Whole Genome Alignment (3/1, 3/3) 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. 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. E. Rivas and S. Eddy. Noncoding RNA gene detection using comparative sequence analysis. BMC Bioinformatics 2(8), 2001. R. Klein and S. Eddy. RSEARCH: Finding homologs of single structured RNA sequences. BMC Bioinformatics 4(44), 2003. lecture notes RNA Secondary Structure Prediction (3/8) Stochastic Context Free Grammars for RNA Structure Modeling (3/8, 3/10, 3/22, 3/24) More on Stochastic Context Free Grammars for RNA Analysis (3/24) Representation, Learning and Inference in Models of Cellular Networks topics: Bayesian networks, module networks, experiment design (active learning), constraints-based modeling 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. C. Yeang, T. Ideker and T. Jaakkola. Physical Network Models. Journal of Computational Biology 11(2-3):243-262, 2004. 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 Module Networks (3/29, 4/5) Physical Network Models (4/7, 4/12) Refining Metabolic Networks (4/12, 4/14) Flux Balance Analysis (4/14, 4/19) Protein Structure Prediction topics: secondary structure prediction, threading, branch and bound search, ROSETTA required reading B. Rost. Protein Structure Prediction in 1D, 2D and 3D. In The Encyclopaedia of Computational Chemistry, 3:2242-2255, 1998. R. Lathrop and T. Smith. Global Optimum Protein Threading with Gapped Alignment and Empirical Pair Score Functions. Journal of Molecular Biology, 255(4):641-665, 1996. recommended reading C. Rohl, C. Strauss, K. Misura and D. Baker. Protein Structure Prediction using Rosetta. Methods in Enzymology, 383:66-93, 2004. lecture notes Introduction to Protein Structure Prediction (4/19, 4/21) Protein Threading (4/21) Biomedical Text Mining topics: named entity recognition, relation extraction required reading recommended reading M. Craven and H. Shatkay. Chapter 4: Information Extraction. From Biomedical Text Mining. MIT Press, forthcoming. 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 Information Extraction from Biomedical Text (5/3, 5/5) Genotype Analysis topics: haplotype inference, genome-wide association studies (GWAS), quantitative trait loci (QTL) mapping recommended reading W. Noble. How does multiple testing correction work?. Nature Biotechnology 27:1135-1137, 2009. lecture notes Linking Genetic Variation to Important Phenotypes (4/28)