Computational Molecular Biology and Genomics Syllabus - Fall 2015

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

  Review biology and algorithms background  
2.  Sep. 3 Global pairwise sequence alignment

PAIRWISE ALIGNMENT NOTES
Alignment example - distance scoring.
Global pairwise alignment
- 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. 8 Global and semiglobal alignment

Alignment example - similarity scoring.

Semi-global alignment:
- 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. 10   Semiglobal and local pairwise alignment

    local alignment examples
    		    
    5.   Sep. 15 Global multiple sequence alignment
    GLOBAL MSA NOTES
    Global multiple alignment using dynamic programming
    - Setubal and Meidanis, 69-72 (electronic reserve)
    - MSA Notes: I   courtesy Dr. M. Singh, Princeton University
    - Durbin, 6.1 -- 6.3 (electronic reserve)
    		 Protein multiple sequence alignment , Do and Katoh, 2008.
    6.  Sep. 17 The progressive multiple alignment heuristic

    Global MSA with the progressive alignment heuristic
    - MSA Notes: II,  courtesy Dr. M. Singh, Princeton University
    - Durbin, 6.4 (electronic reserve)
    		  
    7.   Sep. 22  

    Introduction to Markov chains
    MARKOV CHAIN NOTES
    Markov Chain background
    - Ewens and Grant, 4.4-4.8
    - Durbin et al., 48-51 (Section 3.1) (electronic reserves)
    		 
    8.   Sep. 24 Markov chains, continued.

    		    
    9. Sep. 29 Markov models of sequence evolution, the Jukes Cantor model.

    		   Durbin, et al: 8.2, pp. 193 - 197 only (electronic reserves)  
    10. Oct. 1 Jukes-Cantor model
    SEQUENCE EVOLUTION MODEL NOTES
    		   
    11. Oct. 6   Question/Answer session to prepare for the Exam 1. Bring your questions to class!    
    12. Oct. 8 In-class exam
    This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.
    Location: Scaife hall 125
      Study guide
    		   
    13. Oct. 13 DNA substitution models
      Lecture notes     		   
    14. Oct. 15 Amino acid substitution matrices
    		   
    15. Oct. 20 Substitution matrices
      PAM matrices lecture notes

      PAM30   PAM250,

    Substitution matrices:
    Setubal and Meidanis, pp. 80-84; (electronic reserve)
    Mount, pp. 76-89; (electronic reserve)
    Durbin et al, pp. 14-16 (electronic reserves)
    		  
    16. Oct. 22 BLOSUM matrices   Lecture notes

      BLOSUM62

    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)
    		  
    17. Oct. 27 The BLAST heuristic 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
    		  
    18. Oct. 29 The BLAST heuristic 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.     		 
    19. Nov. 3 BLAST STATISTICS NOTES
    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).
    		 
    20. Nov. 5   BLAST statistics and information content


    		    
    21. Nov. 10 BLAST statistics and information content Slides

    		   
    22. Nov. 12 Local multiple alignment, PSSM's, the Gibbs sampler
    PSSM/GIBBS SAMPLER NOTES
    PSSM example, with and without pseudocounts

    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
    23. Nov. 17 Gibbs sampler

    		   
    24. Nov. 19 Hidden Markov Models (HMMs)

    What is an HMM?
    Ewens and Grant, pp. 327-329 (electronic reserve).
    Durbin, pp. 53-55 (electronic reserve).
    		 
    25. Nov. 24 Class is cancelled.    
      Nov. 26 No class (Thanksgiving Holiday)    
    26. Dec. 1 Hidden Markov models - recognition
    HMM NOTES 1
    Forward example, Viterbi example
    Viterbi, Forward, Backward algorithms
    Durbin, pp. 55 - 61
    (electronic reserve).
    Ewens and Grant, pp. 329-332
    (electronic reserve).

    		 
    27. Dec. 3 Hidden Markov models - recognition

    		   
    28. Dec. 8   Profile HMM's. HMM NOTES 2 (preliminary)
    HMM Topology
    Durbin, pp. 68-71
    (electronic reserve).
    Profile HMMs
    Durbin, pp. 100-110
    (electronic reserve).
    Ewens and Grant, pp. 335 - 337 (electronic reserve).
    		 
    29. Dec. 10 HMM modeling and discovery, cont'd lecture notes
    Parameter estimation, Baum-Welch algorithm
    Durbin, pp. 61-71
    (electronic reserve).
    Ewens and Grant, pp. 329-332
    (electronic reserve).
    		 
    Review Dec 14 MI448, 11:30am - 1:30pm
      Question/Answer session to prepare for the final exam.   Bring your questions to class!
      Study guide
    		  
    Final Exam Dec 15 Final exam   1pm - 4pm

     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 June 22, 2016.
    Maintained by Dannie Durand (durand@cs.cmu.edu).