Computational Molecular Biology and Genomics Syllabus - Fall 2016

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

PS0 due September 6th.
  Review biology and algorithms background  
2.  Sep. 1 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. 6 Global and semiglobal alignment

Alignment example - similarity scoring.

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

    local alignment examples
     
  • 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. 13 Local sequence alignment
    local alignment examples

    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. 15 The progressive multiple alignment heuristic

    PS1 due Friday, Sept 23rd
    Global MSA with the progressive alignment heuristic
    - MSA Notes: II,  courtesy Dr. M. Singh, Princeton University
    - Durbin, 6.4 (electronic reserve)
     
    7.   Sep. 20 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. 22 Markov chains, continued.
      PS1 due tomorrow (9/23) at 4pm

    Lit assignment 1: Due Sep 29
       
    9. Sep. 27 Markov models of sequence evolution, Jukes-Cantor model
    SEQUENCE EVOLUTION MODEL NOTES
    Durbin, et al: 8.2, pp. 193 - 197 only (electronic reserves)  
    10. Sep. 29 Markov models of DNA sequence evolution, cont'd.

      Lit1 due at 4pm

    PS2 due Oct 7th
       
    11. Oct. 4 Markov models of amino acid replacement
      PAM MATRIX LECTURE NOTES

    Substitution matrices:
    Setubal and Meidanis, pp. 80-84; (electronic reserve)
    Mount, pp. 76-89; (electronic reserve)
    Durbin et al, pp. 14-16 (electronic reserves)
     
    12. Oct. 6 Markov models of amino acid replacement
      BLOSUM MATRIX LECTURE NOTES


      PS2 due tomorrow (Oct 7th) at 4pm
    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)
     
    13. Oct. 11 Amino acid substitution matrices, continued.
    Comparing PAM and Blosum matrices.

      PAM30,   BLOSUM62,   PAM250,   BLOSUM45
       
    14. Oct. 13 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
       
    15. Oct. 18 Database searching
        BLAST HEURISTIC NOTES

    Midterm scores
    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
     
    16. Oct. 20 Blast heuristic continued.

    PS3 due Friday, Oct 28
    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.
     
    17. Oct. 25 BLAST STATISTICS LECTURE 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).
     
    18. Oct. 27 Blast statistics and information content, continued.

    PS3 due tomorrow.

    PS4 due Friday, Nov 4

    Lit assignment 2: Due Nov 3rd, 4pm.
       
    19. Nov. 1 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
    20. Nov. 3 The Gibbs Sampler

       
    21. Nov. 8 The Gibbs Sampler

         
    22. Nov. 10 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
      Exam II scores
     
    23. Nov. 15 Hidden Markov Models
    HMM LECTURE NOTES - Part 1

    PS5 due Tuesday, Nov 22
    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).
    24. Nov. 17 HMMs cont'd.   The Forward and Viterbi algorithms
    Forward example
    Viterbi, Forward, Backward algorithms
    Durbin, pp. 55 - 61
    (electronic reserve).
    Ewens and Grant, pp. 329-332
    (electronic reserve).

     
    25. Nov. 22 No class.
      PS5 due at 4pm

    Lit assignment 3: due Nov 29th
       
      Nov. 24 Thanksgiving Holiday: No class

       
    26. Nov. 29 Hidden Markov Models: Decoding
      Viterbi example

    PS6 due Monday, Dec 5
       
    27. Dec. 1 HMMs:
      Modeling, parameter estimation

    HMM LECTURE NOTES - Part 2
    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. 6 Profile HMM's.

    Optional PS7 due Monday, Dec 5 due Tuesday, 13th at 1pm if you are submitting PS 7 for credit.
    Profile HMMs
    Durbin, pp. 100-110
    (electronic reserve).
     
    29. Dec. 8 Profile HMMs
    Multiple alignment using HMMs
    Ewens and Grant, pp. 335 - 337 (electronic reserve).
     
    Review   Dec 14, 12:00 - 2:00 Porter Hall A19A
    Question/Answer session.   Bring your questions with you.
       
    Final Exam   Dec 15, 5:30pm - 8:30pm 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.
     


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