Computational Molecular Biology and Genomics Syllabus - Fall 2014

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. 26 Introduction to computational biology and genomics: part 1 , part 2

  		  Review biology and algorithms background  
2.  Aug. 28 Global pairwise sequence alignment   Lecture notes 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)
    		•   
    3.  Sep. 2 Global and semiglobal alignment
    Lecture notes
  • Alignment example - distance scoring.
  • Alignment example - similarity scoring.
  • Setubal and Meidanis, 56-57 (electronic reserve)
    		•
  • Saving space: Setubal and Meidanis, 58-60; (physical reserve)
  • General gap penalty functions: Setubal and Meidanis, 60-64 (physical reserve)
    • 4.  Sep. 4 Semiglobal and local pairwise alignment
    Lecture notes

  • Local sequence alignment notes,
      courtesy Dr. M. Singh, Princeton University
  • Setubal and Meidanis, p. 55 (electronic reserve)
  • Durbin, pp. 23-24 (electronic reserves)
    		•   
    5.   Sep. 9   Local Pairwise alignment, examples
    Literature assignments,   Lecture notes

    		    
    6.  Sep. 11 Intro to Markov chains
    Lecture notes
    Markov Chain background
    Ewens and Grant, 4.4-4.8
    Durbin et al., 48-51 (Section 3.1) (electronic reserves)
    		 
    7.   Sep. 16 Markov chains, continued.   Lecture notes
      Roig
    		   
    8.   Sep. 18 Markov models of sequence evolution,   the Jukes Cantor model.
    Lecture notes

    		   Durbin, et al: 8.2, pp. 193 - 197 (electronic reserves)  
    9. Sep. 23 Markov models of sequence evolution, cont'd.
    		    
    10. Sep. 25 Markov models of amino acid replacement
      PAM substitution matrices
    New improved lecture notes

      PAM250,   PAM30

    Substitution matrices:
    Setubal and Meidanis, pp. 80-84; (electronic reserve)
    Mount, pp. 76-89; (electronic reserve)
    Durbin et al, pp. 14-16 (electronic reserves)
    		  
    11. Sep. 30 Substitution matrices
      BLOSUM matrices
      BLOSUM45,   BLOSUM80
    BLOSUM Matrices:
    Ewens and Grant, 6.5.2.

    Amino acid substitution matrices from protein blocks, Henikoff S, Henikoff JG., PNAS 89(22):10915-9, 1992 (electronic reserve)
    		  
    12. Oct. 2 BLOSUM matrices
    Lecture notes
    		    
    13. Oct. 7 Data base searching, BLAST statistics
    Lecture notes
    Blast 1990
    Setubal and Meidanis, 84-87 (electronic reserve)
    Basic local alignment search tool, Altschul et al., J. Mol. Bio., 1990 (electronic reserve)
    Strategies for searching sequence databases,Nicholas HB Jr, Ropelewski AJ, Deerfield DW 2nd, Biotechniques 2002 Jun;28(6):1174-8 (electronic reserve)
    Blast statistics and data base searching:
    The statistics of sequence similarity scoresS. F. Altschul
    		  
    14. Oct. 9 The 1990 and 1997 BLAST heuristics
    Lecture notes     		Gapped BLAST : a new generation of protein database search programs. Altschul et al., Nucl. Acids Res. (1997) 25 (17).
    Assigned reading: pp. 3389-3394 only.     		 
    15. Oct. 14 In-class exam
    This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.

      Study guide
    		   
    16. Oct. 16 Gapped BLAST
    lecture notes
    		   
    17. Oct. 21 Class is canceled

    		    
    18. Oct. 23 BLAST statistics and information content

    Lecture notes, slides

    Blast statistics:
    Amino acid substitution matrices from an information theoretic perspective, S. F. Altschul, J. Mol. Bio., 219:555-565, 1991 (electronic reserve).
    A protein alignment scoring system sensitive at all evolutionary distances, S. F. Altschul, J. Mol. Evol., 36:290-300, 1993 (electronic reserve).
    		 
    19. Oct. 28 Local multiple alignment, PSSM's
    slides, PSSM example, with and without pseudocounts
    		   
    20. Oct. 30 Local multiple alignment
    Discovery:   The Gibbs Sampler
    Lecture notes

    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
    21. Nov. 4 Hidden Markov Models
    lecture notes
    What is an HMM?
    Ewens and Grant, pp. 327-329 (electronic reserve).
    Durbin, pp. 53-55 (electronic reserve).
    		Hidden Markov Models in Computational Biology: Applications to Protein Modeling,
    Krogh et al., JMB 235, pp 1501--1531,(1994).
    (electronic reserve).
    22. Nov. 6 Hidden Markov Models, cont'd
    lecture notes
    Calculating the state path that maximizes the data using the Viterbi algorithm
    Durbin, pp. 55 - 57
    (electronic reserve).
    Ewens and Grant, pp. 329-332
    (electronic reserve).
    		 
    23. Nov. 11 HMMs, the Forward and Viterbi algorithms
    lecture notes
    Forward example, Viterbi example
    Viterbi, Forward, Backward algorithms
    Durbin, pp. 55 - 61
    (electronic reserve).
    Ewens and Grant, pp. 329-332
    (electronic reserve).

    		 
    24. Nov. 13 Motif recognition with HMMs lecture notes
    		    
    25. Nov. 18   Hidden Markov Models
       Parameter estimation, topology
       lecture notes
    Parameter estimation, Baum-Welch algorithm
    Durbin, pp. 61-71
    (electronic reserve).
    Ewens and Grant, pp. 329-332
    (electronic reserve).
    HMM topology:
    Durbin, pp. 61-71
    (electronic reserve).
    		 
    26. Nov. 20 In-class exam
    This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.

      Study guide     		   
    27. Nov. 25 Class is cancelled

    		   
      Nov. 27 No class (Thanksgiving Holiday)    
    28. Dec. 2 Profile HMM's. Global alignment with HMM's. lecture notes

    Multiple alignment using HMMs
    Ewens and Grant, pp. 337 - 339 (electronic reserve).
    		 
    29. Dec. 4 Global Multiple Sequence Alignment (MSA), lecture notes



    Global multiple alignment using dynamic programming
    Setubal and Meidanis, 69-72 (electronic reserve)
    MSA Notes: I and II,  courtesy Dr. M. Singh, Princeton University
    Durbin, 6.1 -- 6.4 (electronic reserve)
    		  
    FINAL Dec 11
    1pm - 4pm     		Final exam, Porter Hall A18B
      Study guide

    This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.

    		   


    Return to course homepage
    Last modified February 9, 2015.
    Maintained by Dannie Durand (durand@cs.cmu.edu).