Computational Molecular Biology and Genomics Syllabus - Fall 2009

The materials in the "Assigned Reading" column are directly related to the topics covered in class. Readings under "Additional Topics" are strictly optional and will not be covered on the exams.
      In some cases, the same material is covered in more than one textbook. You have the choice of selecting the text that presents a treatment of the material most to your liking. It is your responsibility to make sure that you understand the material covered in class and you may read as many or as few of these texts needed to achieve that goal.

CLASS
DATE
TOPICS
ASSIGNED READING
ADDITIONAL TOPICS
1.  Aug. 25   Introduction to computational biology and genomics

    PS0 (due Sept. 1). 		   
2.  Aug. 27     Global pairwise sequence alignment
Lecture outline
Alignment examples

  • Global sequence alignment notes,
      courtesy Dr. M. Singh, Princeton University
  • Setubal and Meidanis, 47-55, 89-92, 96-98; (electronic reserve)
  • Durbin, pp. 17-22 (electronic reserves)
    		•
  • Saving space: Setubal and Meidanis, 58-60; (physical reserve)
  • General gap penalty functions: Setubal and Meidanis, 60-64 (physical reserve)
    • 3.  Sept. 1   Global and semi-global pairwise sequence alignment
    Lecture outline
    Alignment examples

    PS0 due.  Solutions
  • Setubal and Meidanis, 56-57; (electronic reserve)
    		•   
    4.  Sept. 3   Local alignment.
    Lecture outline
    Alignment examples

  • Local sequence alignment notes,
      courtesy Dr. M. Singh, Princeton University
  • Setubal and Meidanis, 55; (electronic reserve)
  • Durbin, pp. 23-24 (electronic reserves)
    		•   
    5.   Sept. 8 Global multiple sequence alignment
    711/856 only:
    Literature assignment 1
  • Next-generation Sequencing transforms today's biology,
  • Sequence census methods for functional genomics
    Due Sept. 15
  • Setubal and Meidanis, 69-72 (electronic reserve)
  • Multiple sequence alignment Notes: I and II,  courtesy Dr. M. Singh, Princeton University
  • Durbin, 6.1 -- 6.4(electronic reserves)
    •       		 
    6.   Sept. 10   Global multiple sequence alignment continued
    PS1, (due Sept. 17).
    Alignment template
    Template for pb. 2
  • Protein multiple sequence alignment , Do and Katoh, 2008.
    		•  
    7.  Sept. 15   Phylogenetic Trees, Parsimony methods
    Literature assignment 1 due.  Solutions     		 
    Durbin, et al: (electronic reserves)
    7.1, 7.2:  Background on trees
    7.4:  Parsimony
    Phylogeny notes,pp 1-3 & 17-20,
      Dr. M. Singh, Princeton University
    		   Parsimony, nice examples
  • Mount, pp 248-254(physical reserve)
  • Sankoff's algorithm for inferring ancestral sequences; in Inferring Phylogenies, J. Felsenstein, Sinauer, pp 13-16.
    • 8.   Sept. 17   PS1 due.  Solutions
    Evolutionary trees: Lecture notes
      Branch and bound search, rooting a tree.
    Markov Chain background
    Ewens and Grant, 4.4-4.8
    Durbin et al., 3.1 (electronic reserves)
    Probabilistic models of evolution
    Durbin, et al: 8.1, 8.2 (electronic reserves)
    Phylogeny notes, pp. 13 - 17,   courtesy Dr. M. Singh, Princeton University
    		 
    9.   Sept. 22   Distance-based methods
      Jukes-Cantor model; correcting for multiple substitutions. Lecture outline     		Distance-based methods
  • Durbin, et al: 7.3(electronic reserves)
  • Phylogeny notes, pp.4-13,
      courtesy Dr. M. Singh, Princeton University
    		•  
    10. Sept. 24 Class is canceled
      PS2, (due October 6th).
      711/856 only:
    Literature assignment 2
  • Schloss, 2005
  • Raes, 2007
    		•    
    11. Sept. 29 Distance-based phylogeny reconstruction. Lecture outline    
    12. Oct. 1 Distance-based methods
      Minimum evolution, UPGMA and Neighbor Joining Lecture outline
      Literature assignment 2 due.  Solutions     		 
  • Durbin, et al: 7.8, NJ proof. (physical reserves)
    • 13. Oct. 6 PS2 due.   PS2 solutions
    Maximum likelihood estimation;         		Phylogeny Estimation and Hypothesis Testing using Maximum Likelihood., pp. 1-8
    J. P. Huelsenbeck and K. A. Crandall, Ann. Rev. Ecol. Syst. 1997, 28:437-66     		Complexity results:
  • On the Approximability of Numerical Taxonomy: (Fitting Distances by Tree Metrics), Agarwala et al. , (SODA '96) (electronic reserve)
  • Efficient Algorithms for Inverting Evolution, Farach and Kannan, (STOC '96)
    • 14. Oct. 8   Introduction to local MSA    
    15. Oct. 13  
    Position Specific Scoring Matrices
    A PSSM for the WEIRD motif
    A PSSM with pseudocounts

    Gibbs Sampler. Lecture notes forthcoming.

    Office hours will be held Wednesday from 2pm - 5pm in MI646. No office hours on Thursday.
    Gibbs sampler
    Ewens and Grant, pp. 211-215.    Electronic reserve.
    Theoretical framework, convergence proofs
    Ewens and Grant, 10.5.2, Physical reserves.
    Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment, Lawrence et al., Science. 1993 262(5131):208-14.
    Explaining the Gibbs sampler, G. Casella & E. I. George, The American Statistician, 46:167-174, 1992

    Other motif discovery methods
    16. Oct. 15   Midterm Exam
    This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.     		   
    17. Oct. 20 Gibbs Sampler, Lecture notes    
    18. Oct. 22 Introduction to Hidden Markov Models Lecture notes

      711/856 only:
    Literature assignment 3
  • Desalle & Schierwater, 08
  • Blackstone, 09
  • Telford, 09
    		•    
    19. Oct. 27 Hidden Markov Models II
       Viterbi, Forward, Backward algorithms
    Lecture notes
    Viterbi algorithm example
    Forward algorithm example
    Viterbi, Forward, Backward algorithms
    Durbin, pp 55 - 61.
    Ewens and Grant, pp. 329-332 Electronic reserves.
    		Hidden Markov Models in Computational Biology: Applications to Protein Modeling,
    Krogh et al., JMB 235, pp 1501--1531,(1994).
    Available through electronic reserves.
    20. Oct. 29 Hidden Markov Models II
       Forward & Backward algorithms, posterior decoding.
    Lecture notes
    		   
    21. Nov. 3   Literature assignment 3 due.    
    22. Nov. 5 Parameter estimation, Baum-Welsh algorithm
    Lecture notes
     
    Parameter estimation, Baum-Welsh algorithm
    Durbin, pp 61-71
    Ewens and Grant, pp. 329-332 Electronic reserves.
    		 
    23. Nov. 10  
    HMM topology: Durbin, pp 61-71 Electronic reserves.
    Profile HMMs
    Durbin, pp 100 - 113.
    Ewens andGrant, pp. 335-337 Electronic reserves.
    Multiple alignment using HMMs
    Ewens and Grant, pp. 337 - 339 Electronic reserves.
    		 
    24. Nov. 12      
    25. Nov. 17      
    26. Nov. 19      
    27. Nov. 24      
      Nov. 26 No class (Thanksgiving Holiday)

    		    
    28. Dec. 1      
    29. Dec. 3      
      Dec. 7   Final Exam:   1pm - 4pm.
    This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.     		   
    To view online lectures in Quicktime format, you will need to have within your browser the QuickTime plug-in, and select it as the player for all media files. You can download the QuickTime Movie player for a PC or Mac free of charge at: http://www.apple.com/quicktime/download/index.html.



    Return to course homepage
    Last modified: Sept. 27, 2009.
    Maintained by Dannie Durand (durand@cs.cmu.edu).