Syllabus, Readings and Lecture Notes

• Background: 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
    • Nucleic Acids Research Database Issue and Database Collection
    • Nucleic Acids Research Web Server Issue
    • Bioinformatics Links Directory
    • Tutorial on Computational Complexity
  • lecture notes
    • Course Overview (9/6)
    • Introduction to Molecular Biology (9/8, 9/13)
    • Introduction to Genomic Data (9/13)
    • Primer on Probability for Discrete Variables (10/4)

• Biological Sequence Assembly
  • topics: Fragment assembly, Sequencing by hybridization, Overlap-layout-consensus
  • required reading:
    • M. Pop Genome assembly reborn: recent computational challenges. Briefings in Bioinformatics 10(4):354-366, 2009.
  • lecture notes
    • Sequence Assembly (9/15, 9/20)

• 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 Alignment (Part 1) (9/22)
    • Pairwise Alignment (Part 2) (9/27) (updated 9/29)
    • Heuristic Methods for Sequence Database Searching (9/29, 10/6)
    • Alignment Statistics and Substitution Matrices (10/6)

• 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 (Part 1) (10/11)
    • Markov Chain Models (Part 2) (10/18)
    • Hidden Markov Models (Part 1) (10/18, 10/20) (updated 10/20)
    • Hidden Markov Models (Part 2) (10/25)
    • Applications of HMMs in Computational Biology (10/27)

• 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/1)
    • Distance-Based Approaches to Inferring Phylogenetic Trees (11/1, 11/3) (updated 11/2)
    • Parsimony-Based Approaches to Inferring Phylogenetic Trees (11/3, 11/8) (updated 11/10)
    • Multiple Sequence Alignment (11/15)

• 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
    • C. Manning, P. Raghavan and H. Schutze. Chapter 16: Flat Clustering. Introduction to Information Retrieval, Cambridge University Press, 2008.
    • C. Manning, P. Raghavan and H. Schutze. Chapter 17: Hierarchical Clustering. Introduction to Information Retrieval, Cambridge University Press, 2008.
  • recommended reading
    • Spotted Array Flash Animation Tutorial
    • 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
    • Measuring Transcriptomes with RNA-Seq (11/17)
    • Microarrays, RNA-Seq and other High-Throughput Methods (11/22)
    • Clustering Gene Expression Data (11/29, 12/1)

• Inferring and Modeling Cellular Networks
  • topics: Bayesian networks, module networks, exact and approximate inference methods, parameter and structure learning
  • required reading
    • N. Friedman. Inferring cellular networks using probabilistic graphical models. Science 303(5659): 799-805, 2004.
    • 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, 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
    • 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.
  • lecture notes
    • lecture by David Baumler on Metabolic Modeling of Bacteria (10/13)
    • Introduction to Cellular Networks (12/6)
    • Bayesian Networks Applied to Modeling Cellular Networks (12/6)
    • Bayesian Network Structure Learning (Part 1) (12/8)
    • Bayesian Network Structure Learning (Part 2) (12/13)
    • Inference in Bayesian Networks (12/15)

  ---