Computational Molecular Biology and Genomics Syllabus - Fall 2013

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. 27 Introduction to computational biology and genomics:   part 1 , part 2
PS0 (due Sept. 3).  		 Review biology and algorithms background  
2.  Aug. 29 Global pairwise sequence 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. 3   Semiglobal pairwise sequence alignment
  • Lecture notes
  • Alignment example - distance scoring.
  • Alignment example - similarity scoring.

    PS0 DUE
    		•  
  • 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. 5 Local pairwise alignment
    Lecture notes

    PS1 (due Sept. 13).     		 
  • Local sequence alignment notes,
      courtesy Dr. M. Singh, Princeton University
  • Setubal and Meidanis, 55; (electronic reserve)
  • Durbin, pp. 23-24 (electronic reserves)
    		•   
    5.   Sep. 10 Pairwise alignment follow up.
    Literature assignments, lecture notes

    Lit assignment 0 , due Sep19
    		   
    7.  Sep. 17 Intro to Markov chains
    Lecture notes
    Markov Chain background
    Ewens and Grant, 4.4-4.8
    Durbin et al., 3.1 (electronic reserves)
    		 
    8.   Sep. 19 Markov chains, continued, lecture notes


    Lit0 due
    Lit assignment 1 (due Sep26)
    		   
    9.   Sep. 24 Markov models of sequence evolution,
    the Jukes Cantor model.
    lecture notes
    		 Durbin, et al: 8.2, pp. 193 - 197(electronic reserves)  
    10. Sep. 26 Substitution matrices
      PAM matrices lecture notes

      PAM250,   PAM30

    Lit1 due

    PS2 (due Oct. 10)

    Substitution matrices:
    Setubal and Meidanis, 80-84; (electronic reserve)
    Mount, pp 76-89; (electronic reserve)
    Durbin et al, pp 14-16 (electronic reserves)
    		  
    11. Oct. 1 Substitution matrices
      BLOSUM matrices lecture notes
    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. 3 BLAST I
    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 scores S. F. Altschul
    		 
    13. Oct. 8 Gapped and two-hit BLAST
    lecture notes
    		   
    14. Oct. 10 BLAST

    PS2 due     		   
    15. Oct. 15 Midterm Exam
    This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.     		   
    16. Oct. 17 BLAST statistics and information content
    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)
    		  Statistical Methods in Bioinformatics, W. Ewens and G. Grant (Physical reserves)

    Other BLAST references
    17. Oct. 22 BLAST statistics and information content

    Midterm review
    		    
    18. Oct. 24   Local multiple alignment, PSSM's
    lecture notes
    A PSSM for the WEIRD motif

    		   
    19. Oct. 29 Local multiple alignment
        A WEIRD PSSM with pseudocounts
        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
    20. Oct. 31 Gibbs sampler, cont'd
    Lecture notes

    PS3 (due Nov. 12th)

    711/856 only:
    Lit 3 (due Nov 15th)     		 
    21. Nov. 5      
    22. Nov. 7 Hidden Markov Models
    lecture notes
    What is an HMM?
    Ewens and Grant, pp. 327-329.
    Durbin, pp 53-55.
    		Hidden Markov Models in Computational Biology: Applications to Protein Modeling,
    Krogh et al., JMB 235, pp 1501--1531,(1994).
    Available through electronic reserves.
    23. Nov. 12 HMMs, the Viterbi algorithm
    lecture notes
    Viterbi example
    Calculating the state path that maximizes the data using the Viterbi algorithm
    Durbin, pp 55 - 57
    Ewens and Grant, pp. 329-332 Electronic reserves.
    		 
    24. Nov. 14   HMMs, the Forward and Backward algorithms
    lecture notes
    Forward example

    PS 4 (due Nov 26th)

    711/856 only:
    Lit 4 (due Nov 26th)
    Viterbi, Forward, Backward algorithms
    Durbin, pp 55 - 61.
    Ewens and Grant, pp. 329-332 Electronic reserves.

    		 
    25. Nov. 19   Hidden Markov Models
       Posterior decoding, Parameter estimation
    lecture notes
    Parameter estimation, Baum-Welch algorithm
    Durbin, pp 61-71
    Ewens and Grant, pp. 329-332 Electronic reserves.
    		 
    26. Nov. 21 Hidden Markov Models
      Topology
    lecture notes
    HMM topology:
    Durbin, pp 61-71 Electronic reserves.
    		  
    27 Nov. 26 Class is cancelled

    PS4, Lit4 due today at 5pm.     		   
      Nov. 28 No class (Thanksgiving Holiday)    
    28. Dec. 3 Hidden Markov Models for global multiple alignment

    711/856 only:
    Lit 5 (due Dec 6th)
    Multiple alignment using HMMs
    Ewens and Grant, pp. 337 - 339 Electronic reserves.
    		 
    29. Dec. 5 Global Multiple Sequence Alignment (MSA) lecture notes

    PS5 (due 5pm Dec. 9th)
    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 reserves)
    		 Protein multiple sequence alignment , Do and Katoh, 2008.
    FINAL Dec. 12      


    Return to course homepage
    Last modified June 12, 2013.
    Maintained by Dannie Durand (durand@cs.cmu.edu).