Computational Molecular Biology and Genomics Syllabus - Fall 2018

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. 28
  • Introduction to computational biology and genomics
  • Pairwise sequence alignment

    PS0 due Tuesday, Sept. 3rd in class
    		•   Review biology and algorithms background  
    2.  Aug. 30 Global pairwise sequence alignment

    SEQUENCE ALIGNMENT NOTES
       Alignment example - distance scoring.
       Alignment example - similarity scoring.
    Global pairwise alignment
    Setubal and Meidanis 47-55, 89-92, 96-98; (electronic reserve)
    - Durbin, pp. 17-22; (electronic reserves)
    		  
    3.  Sep. 4 Global and semiglobal alignment

    PS0 DUE IN CLASS
    Semi-global alignment:
    Setubal and Meidanis, 56-57 (electronic reserve)
    4.  Sep. 6 Semiglobal and local pairwise alignment

    Local alignment examples

    PS1 due 2pm FRIDAY, Sep. 13th
    Alignment template
    Local pairwise alignment
    Setubal and Meidanis, p. 55 (electronic reserve)
    Durbin, pp. 23-24 (electronic reserves)
    		  
    5.   Sep. 11   Global multiple sequence alignment


    Global multiple alignment using dynamic programming
    - Setubal and Meidanis, 69-72 (electronic reserve)
    - Durbin, 6.1 -- 6.3 (electronic reserve)
    		  
    6.  Sep. 13 The progressive multiple alignment heuristic

    PS1 due at tomorrow (Friday) 2pm in MI646

    PS2 due Friday, Sept 21st.
    Alignment template


    711 Assignment 1 due Friday, September 21st  
    Global MSA with the progressive alignment heuristic
    - Durbin, 6.4 (electronic reserve)
    		 Protein multiple sequence alignment , Do and Katoh, 2008.
    7.   Sep. 18 Introduction to Markov chains
    SEQUENCE EVOLUTION MODEL NOTES Includes Markov chains.

    Markov Chain background
    - Ewens and Grant, 4.4-4.8
    - Durbin et al., 48-51 (Section 3.1) (electronic reserves)
    		 
    8.   Sep. 20 Markov models, continued.

    Problem set 2, Seven11 assignment 1 due tomorrow (Friday) at 1:30pm

    PS3 (due Thurs, Sep. 27, in class).
    		   
    9. Sep. 25 Markov models of sequence evolution, Jukes-Cantor model

    		 Durbin, et al: 8.2, pp. 193 - 197 only (electronic reserves)  
    10. Sep. 27 Markov models of sequence evolution, cont'd

    PS3 due in class

    PS4 (due 3pm, Oct 5th, in MI646).
    		   
    11. Oct. 2 More complex models of sequence evolution.

    		   
    12. Oct. 4 Log-odds scoring
    PS4 due in tomorrow (Friday)

    		    
    13. Oct. 9 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

    		   
    14. Oct. 11 No class.

    PS5 (due FRIDAY 3pm, Oct 19th, in MI646).

    		   
    15. Oct. 16 AMINO ACID SUBSTITUTION MATRIX NOTES

    Today's slides
    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. 18 Amino acid subst. matrices cont'd

    PS5 due tomorrow

    		   
    17. Oct. 23 Amino acid subst. matrices cont'd
      PAM250,   BLOSUM62   PAM30


    711 Assignment 2 due Tues, Oct.30 in class.  
    Page & Holmes, pp.187-189.
    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)
    		  
    18. Oct. 25 Blast heuristics
    BLAST LECTURE NOTES

    PS6 (due FRIDAY 3pm, Nov 2nd, in MI646).
    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
    		  
    19. Oct. 30 Gapped BLAST slides

    Seven11 Assignment 2 deadline extended to Friday
    		  
    20. Nov. 1 BLAST statistics slides

      Seven11-2 and PS6 due tomorrow at 3pm in MI646

    		 
    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).
    21. Nov. 6 Local multiple alignment
    PSSM, GIBBS SAMPLER LECTURE 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
    22. Nov. 8 The Gibbs Sampler

    711 Assignment 3 due FRIDAY Nov. 16th, 3pm.  

    PS7 (due Tues 2pm, Nov 20th).   Worksheet for Blast output.
    		   
    23. Nov. 13 Hidden Markov Models
      HMM LECTURE NOTES
    What is an HMM?
    Ewens and Grant, pp. 327-329 (electronic reserve).
    Durbin, pp. 53-55 (electronic reserve).
    24. Nov. 15 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

    		   
    25. Nov. 20 711 Assignment 4 due Fri Nov 30, 2018.
    Reading: Altschul 05.

    		   
      Nov. 22   Thanksgiving Holiday: No class

      PS8 (due 3pm, Fri, Nov 30th).

    		   
    26. Nov. 27 Hidden Markov Models: Recognition slides


      Forward example
    Viterbi, Forward, Backward algorithms
    Durbin, pp. 55 - 61
    (electronic reserve).
    Ewens and Grant, pp. 329-332
    (electronic reserve).

    		 
    27. Nov. 29 Hidden Markov Models: Recognition
      Viterbi example

    Due tomorrow at 3pm in MI646:
  • Seven11-4
  • PS8

    		•    
    28. Dec. 4 HMM design: Parameter estimation, topology

    Optional PS9 due Tuesday, Dec. 11th at 3pm if you are submitting PS 9 for credit.


    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).
    		 
    29. Dec. 6 Profile HMMs, Hidden Markov Models for global multiple alignment
    slides

    Profile HMMs
    Durbin, pp. 100-110
    (electronic reserve).
    Multiple alignment using HMMs
    Ewens and Grant, pp. 335 - 337 (electronic reserve).
    		 
    Final exam   TBA


    		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 April 3, 2019.
    Maintained by Dannie Durand (durand@cs.cmu.edu).