Biostatistics & Medical Informatics 576
Computer Sciences 576
Introduction to Bioinformatics (Fall 2009)

Syllabus, Readings and Lecture Notes

• Introduction to Molecular Biology, Genomics, Bioinformatics, Probability
  • topics: DNA, RNA, proteins, the Central Dogma, RNA processing in eukaryotes, networks, available genomics data, basic probability theory for discrete variables
  • required reading
    • L. Hunter. Life and Its Molecules: A Brief Introduction. AI Magazine 25(1):9-22, 2004.
  • recommended reading
    • Human Genome Project: Frequently Asked Questions
    • NAR Molecular Biology Database Collection
  • lecture notes
    • Course Overview (9/2)
    • Introduction to Molecular Biology and Genomics (9/3, 9/9)

• Biological Sequence Assembly
  • topics: Fragment assembly, Sequencing by hybridization, Overlap-layout-consensus
  • required reading:
    • S. Batzoglou Algorithmic challenges in mammalian whole genome assembly In Dunn M, Jorde L, Little P, Subramaniam S, editors. Encyclopedia of genomics, proteomics and bioinformatics. Hoboken (New Jersey): John Wiley and Sons, 2005.
  • lecture notes
    • Sequence Assembly (9/11, 9/14, 9/16, 9/18)

• Pairwise Sequence Alignment
  • topics: dynamic programming methods for global and local alignment, linear and affine gap penalty functions, the BLAST algorithm, alignment statistics, substitution matrices
  • required reading
    • Sections 2.1-2.4 in Durbin et al.
    • Sections 2.5, 2.7, 2.8 in Durbin et al.
    • S. Altshul, T. Madden, A. Schaffer, J. Zhang, Z. Zhang, W. Miller and D. Lipman. Gapped BLAST and PSI-BLAST: A New Generation of Protein Database Search Programs. Nucleic Acids Research 25(17):3389-3402, 1997.
  • lecture notes
    • Pairwise Sequence Alignment/Dynamic Programming (9/21,9/23,9/25,9/28,10/2)
    • Heuristic Methods for Sequence Database Searching (10/2,10/7)
    • Primer on Probability for Discrete Variables (10/2,10/9)
    • Alignment Statistics and Substitution Matrices (10/5,10/7)

• Probabilistic Sequence Models
  • topics: Markov chains, high-order Markov models, inhomogenous Markov models, hidden Markov models, Forward/Backward/Viterbi algorithms, applications to gene finding and motif modeling
  • required reading
    • Sections 3.0, 3.1, 3.5 in Durbin et al.
    • Sections 3.2, 3.3 in Durbin et al.
  • lecture notes
    • Markov Chain Models (10/9,10/12)
    • Hidden Markov Models (10/14, 10/16, 10/19, 10/21, 10/23, 10/26)
    • Applications of HMMs in Computational Biology (10/28)

• Multiple Sequence Alignment and Phylogenetic Tree Inference
  • topics: dynamic programming for MSA, heuristic methods for MSA, profile HMMs, distance based phylogeny methods, UPGMA, neighbor-joining, parsimony based algorithms, Fitch's algorithm, weighted parsimony, nearest-neighbor interchange, branch and bound search
  • required reading
    • Chapter 6 in Durbin et al.
    • Sections 7.1-7.6 in Durbin et al.
  • lecture notes
    • Introduction to Phylogenetic Trees (11/2) (Slides updated: 11/9)
    • Parsimony-Based Approaches to Inferring Phylogenetic Trees (11/4,11/9) (Slides updated: 11/9)
    • Maximum Likelihood and Bootstrap Methods for Inferring Phylogenetic Trees (Guest lecturer: Cecile Ane) (11/6)
    • Distance-Based Approaches to Inferring Phylogenetic Trees (11/11, 11/13) (Slides updated: 11/9)
    • Multiple Sequence Alignment (11/16, 11/18) (Slides updated: 11/20)

• Analyzing Data from Microarray, SNP-chip, and other High-Throughput Experiments
  • topics: high-throughput technologies, detecting diffferential expression, multiple hypothesis testing and false-discovery-rate methods, clustering algorithms, biclustering, classification algorithms
  • required reading
    • Spotted Array Flash Animation Tutorial
    • C. Manning and H. Schutze. Chapter 15: Clustering. Foundations of Statistical Natural Language Processing, MIT Press, 1999.
  • recommended reading
    • M. Eisen, P. Spellman, P. Brown, D. Botstein. Cluster Analysis and Display of Genome-Wide Expression Patterns. Proceedings of the National Academy of Sciences, 95:14863-14868, 1998.
    • M. Molla, M. Waddell, D. Page and J. Shavlik. Using Machine Learning to Design and Interpret Gene-Expression Microarrays AI Magazine, 25(1):23-44, 2004.
  • lecture notes
    • Microarrays and Other High-Throughput Methods (11/20) (Slides updated: 11/20)
    • Clustering Gene-Expression Data (11/23,11/25)

• Inferring and Modeling Cellular Networks
  • topics: Bayesian networks, module networks, exact and approximate inference methods, parameter and structure learning
  • required reading
    • N. Friedman, M. Linial, I. Nachman, D. Pe'er. Using Bayesian networks to analyze expression data. Journal of Computational Biology 7(3-4):601-620, 2000.
      Alternate link
    • K. Sachs, O. Perez, D. Pe'er, D. Lauffenburger, G. Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science 308(5721):523-529, 2005.
  • recommended reading
    • N. Friedman, I. Nachman and D. Pe'er. Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm In Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence 1999.
    • I. Nachman, A. Regev, and N. Friedman. Inferring quantitative models of regulatory networks from expression data. Bioinformatics 20(Suppl. 1):i248-i256, 2004.
  • lecture notes
    • Introduction to Biological Networks (11/30)
    • Bayesian Networks Applied to Modeling Cellular Networks (12/2,12/4,12/7)
    • Inference in Bayesian Networks (12/9,12/11)

• Review of topics for final exam (12/14)