Computational Molecular Biology and Genomics Syllabus - Fall 2017

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. 29 PS0 out Introduction to computational biology and genomics part 1 , part 2

PS0 due September 5th in class 		  Review biology and algorithms background  
2.  Aug. 31 Global pairwise sequence alignment

SEQUENCE 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. 5 Global and semiglobal alignment
Alignment example - similarity scoring.

PS0 DUE IN CLASS
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. 7 Semiglobal and local pairwise alignment

    Local alignment examples

    PS1 due September 14th
    Local pairwise alignment
    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. 12   Local sequence alignment,
    local alignment examples

    Global multiple sequence alignment


    711 Assignment 1 due September 28th
    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)
    		  
    6.  Sep. 14 The progressive multiple alignment heuristic

    PS1 due at 4pm.


    PS2 (due Friday, Sept 22nd).
    Global MSA with the progressive alignment heuristic
    - MSA Notes: II,  courtesy Dr. M. Singh, Princeton University
    - Durbin, 6.4 (electronic reserve)
    		 Protein multiple sequence alignment , Do and Katoh, 2008.
    7.   Sep. 19 Progressive multiple sequence alignment, continued.
      See Lecture 6 for slides.     		   
    8.   Sep. 21 Introduction to Markov chains
    SEQUENCE EVOLUTION MODEL NOTES Includes Markov chains.

    PS2 due tomorrow, Sep 22.
    Markov Chain background
    - Ewens and Grant, 4.4-4.8
    - Durbin et al., 48-51 (Section 3.1) (electronic reserves)
    		 
    9. Sep. 26 Markov chains, continued

    PS3 (due Friday, Oct. 3).     		   
    10. Sep. 28 Markov models of sequence evolution, Jukes-Cantor model

      711 Assignment 1 due
    		 Durbin, et al: 8.2, pp. 193 - 197 only (electronic reserves)  
    11. Oct. 3 Markov models of nucleotide subtitution, continued.

      PS3 due at 4pm     		 
    12. Oct. 5 In-class exam I
    This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.

      Study guide     		 
    13. Oct. 10 Markov models of nucleotide subtitution, continued.

    		   
    14. Oct. 12 Markov models of amino acid replacement

    PS4 (due Friday, Oct. 20)     		   
    15. Oct. 17 AMINO ACID SCORING MATRICES
    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. 19 PS4 due tomorrow

    		   
    17. Oct. 24 Blast heuristics

    BLAST 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)
    Blast 1997
    Gapped BLAST Altschul et al., Nucl. Acids Res., 1997, pp. 1-6
    NAR or PMC
    		 
    18. Oct. 26 Blast statistics and information content
    Blast statistics:
    Blast statistics and data base searching:
    The statistics of sequence similarity scores S. F. Altschul
    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. 31 Blast statistics and information content.

    		    
    20. Nov. 2 Local multiple alignment, PSSM's, the Gibbs sampler
    slides

    PSSM example, with and without pseudocounts

    PS5 (due Friday, Nov. 10, 2pm)
    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. 7 PSSM, GIBBS SAMPLER LECTURE NOTES



    711 Assignment 2, due Nov. 17th     		     
    22. Nov. 9 Hidden Markov Models: Introduction
    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).
    23. Nov. 14 In-class exam II
    This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.
      Study guide

    24. Nov. 16 HIDDEN MARKOV MODELS LECTURE NOTES

    HMMs cont'd.   Recognition: the Forward algorithm
    Forward example
    Viterbi, Forward, Backward algorithms
    Durbin, pp. 55 - 61
    (electronic reserve).
    Ewens and Grant, pp. 329-332
    (electronic reserve).

    		 
    25. Nov. 21 No class.

    711 Assignment 3 due WEDNESDAY Nov. 29th, 4pm     		   
      Nov. 23 Thanksgiving Holiday: No class
          		   
    26. Nov. 28 Hidden Markov Models: Decoding
      Viterbi example

    PS6, due Thurs, Dec 7th,     		   
    27. Nov. 30 HMMs:   Modeling

    711 Assignment 4, due Friday, Dec 8th, 4pm.
    HMM Topology
    Durbin, pp. 68-71
    (electronic reserve).
    Parameter estimation, Baum-Welch algorithm
    Durbin, pp. 61-71
    (electronic reserve).
    Ewens and Grant, pp. 329-332
    (electronic reserve).
    		 
    28. Dec. 5 Profile HMM's.

    Profile HMMs
    Durbin, pp. 100-110
    (electronic reserve).
    		 
    29. Dec. 7 Profile HMMs, Hidden Markov Models for global multiple alignment

    Optional PS7, due Dec 13th at 1pm if you are submitting PS 7 for credit.

    Multiple alignment using HMMs
    Ewens and Grant, pp. 335 - 337 (electronic reserve).
    		 
    Final exam   Dec 17, 1pm-- 4pm
     GHC 4215     		Final exam  
      This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.

    		  Study guide
      The exam covers the entire semester, but with a strong emphasis on the last third of the course.
    		  The time and date of the final exam are determined by the registrar's office and are beyond my control. You must take the final exam at the time scheduled. Until the date of the final is determined, you should not make plans to leave for winter vacation before the end of the exam period.


    Return to course homepage
    Last modified Dec. 7, 2017.
    Maintained by Dannie Durand (durand@cs.cmu.edu).