Computational Molecular Biology and Genomics Syllabus - Fall 2011

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
PS0 (due Sept. 6). 		  Review biology and algorithms background  
2.  Sep. 1 Global pairwise sequence alignment
  • Lecture outline
  • Alignment examples (distance)
  • 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)
    		•
  • Saving space: Setubal and Meidanis, 58-60; (physical reserve)
  • General gap penalty functions: Setubal and Meidanis, 60-64 (physical reserve)
    • 3.  Sep. 6 Semiglobal pairwise sequence alignment
  • Global alignment examples (similarity)
  • Semiglobal alignment examples

    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. 8   Local pairwise alignment
    PW alignment examples

    PS1 due Sept. 20.
  • Local sequence alignment notes,
      courtesy Dr. M. Singh, Princeton University
  • Setubal and Meidanis, 55; (electronic reserve)
  • Durbin, pp. 23-24 (electronic reserves)
    		•   
    5.   Sep. 13   Global Multiple Sequence Alignment  
  • Setubal and Meidanis, 69-72 (electronic reserve)
  • Multiple sequence alignment Notes: I and II,&nb\ sp; courtesy Dr. M. Singh, Princeton University
  • Durbin, 6.1 -- 6.4(electronic reserves)
  • Protein multiple sequence alignment , Do and Katoh, 2008.
    		•  
  • On the Design of Optimization Criteria for MSA, Durand & Farach-Colton, In Biological Evolution and Statistical Physics, Laessig & Valleriani
  • Strategies for multiple sequence alignment, Nicholas HB Jr, Ropelewski AJ, Deerfield DW 2nd, Biotechniques 2002 Mar;32(3):572-4 (electronic reserve)
    • 6.   Sep. 15 Intro to Markov chains, notation

    Markov Chain background
    Ewens and Grant, 4.4-4.8
    Durbin et al., 3.1 (electronic reserves)
    		 
    7.  Sep. 20 Local multiple alignment lecture notes
    PS1 due

    711/856 only:
    Literature assignment 1, Due Sept 27.
    Hawkins et al., 2010.         		   
    8.   Sep. 22 Position Specific Scoring Matrices (PSSMs), lecture notes
    A PSSM for the WEIRD motif
    A PSSM with pseudocounts

    		   
    9.   Sep. 27 Local MSA, discovery.
  • The Gibbs Sampler

    Literature assignment 1 due.
    • 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
    10. Sep. 29 Intro to Hidden Markov Models lecture notes

    PS2a (due Oct. 6).     		   
    11. Oct. 4   Hidden Markov Models
    lecture notes

    Viterbi algorithm exercise
    Viterbi algorithm example
    What is an HMM?
    Ewens and Grant, pp. 327-329
    Durbin, pp 53 - 55
    Calculating the state path that maximizes the data using the Viterbi algorithm
    Durbin, pp 55 - 57
    Ewens and Grant, pp. 329-332 Electronic reserves.
    		Hidden Markov Models in Computational Biology: Applications to Protein Modeling,
    Krogh et al., JMB 235, pp 1501--1531,(1994).
    Available through -- --electronic reserves.
    12. Oct. 6 Science2011   (map)
        NO CLASS.
    PS2a due


    PS2b (due Oct. 13).

    711/856 only:   Literature assignment 2,   Due Oct. 14
    Edgar, 2009
    Viterbi, Forward, Backward algorithms
    Durbin, pp 55 - 61.
    Ewens and Grant, pp. 329-332 Electronic reserves.

    HMM model structure
    Durbin, pp 68 - 70. Electronic reserves.
    		 
    13. Oct. 11 Hidden Markov Models
      Viterbi and Forward algorithms
    lecture notes

      Today's examples
    		    
    14. Oct. 13   Hidden Markov Models

    PS2b due


    Lit assignment 2 due Friday the 14th.     		   
    15. Oct. 18   Hidden Markov Models
          		   
    16. Oct. 20 Midterm Exam
    This exam is closed book. You may bring two pages (or one page, front and back) of your own notes.     		   
    17. Oct. 25 Profile HMMs, lecture notes
    Profile HMMs
    Durbin, pp 100 - 113.
    Ewens and Grant, pp. 335-337 Electronic reserves.
    Multiple alignment using HMMs
    Ewens and Grant, pp. 337 - 339 Electronic reserves.
    		 
    18. Oct. 27 Substitution Matrices
      PAM matrices
     Lecture notes

      PAM250,   PAM30

    Substitution matrices:
    Setubal and Meidanis, 80-84; (electronic reserve)
    Mount, pp 76-89; (electronic reserve)
    Durbin et al, pp 14-16 (electronic reserves)
    		  
    19. Nov. 1 Substitution Matrices
      BLOSUM matrices
    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)
    		  
    20. Nov. 3   BLAST,   Lecture notes

      711/856 only:
    Literature assignment 3,   Due Nov. 15
  • Schloss, 2005
  • Raes, 2007
    • Setubal and Meidanis, 84-87 (electronic reserve)
    • Basic local alignment search tool, Altschul et al. , J. Mol. Bio., 1990 (electronic reserve)
    		 
    21. Nov. 8 Blast, gapped and ungapped.
    Lecture notes

     BLAST home page

    Two recommended tutorials for students unfamiliar with BLAST
    Blast statistics and data base searching:
    The statistics of sequence similarity scores S. F. Altschul  

    Strategies for searching sequence databases, Nicholas HB Jr, Ropelewski AJ, Deerfield DW 2nd, Biotechniques 2002 Jun;28(6):1174-8 (electronic reserve)
    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
    22. Nov. 10 Blast statistics, information content.
    Lecture notes

    PS3a (due Nov 22).

    		   
    23. Nov. 15 Introduction to trees.
    Lecture notes

    Lit Assignment 3 due.     		Navigating tree space pp. 37-44
    		 
    24. Nov. 17 Trees: Maximum parsimony
    Lecture notes

    Durbin, et al: (electronic reserves)
    7.1, 7.2:  Background on trees
    7.4:  Parsimony
    Phylogeny notes,pp 1-3 & 17-20,
      Dr. M. Singh, Princeton University
    		 Sankoff's algorithm for inferring ancestral sequences; in Inferring Phylogenies, J. Felsenstein, Sinauer, pp 13-16.  
    25. Nov. 22 No class

    PS3a due in MI-464 before 5pm or electronically: comp-bio@cs.cmu.edu.

    PS3b (due Dec. 3).


    		   
      Nov. 24 No class (Thanksgiving Holiday)    
    26. Nov. 29 Trees: Distance-based methods.
    Jukes Cantor model.
    Lecture outline
    		 Distance-based methods
  • Durbin, et al: 8.1-8.2(electronic reserves)
  • Phylogeny notes, pp.14-17,
      courtesy Dr. M. Singh, Princeton University
    		•   
    27. Dec. 1 Trees: Additive and ultrametric distances:   Lecture notes

    PS4 (due Dec 9th).



    711/856 only:
    Lit. assignment 4,   Due Dec 9th
  • Genome 10K
  • Stoeckle 03
    		• Felsenstein*,   Ch. 11 UPGMA and NJ, pp. 161-169  
    28. Dec. 6 Trees: UPGMA and NJ:   Lecture notes
    UPGMA,   NJ     		   
    29. Dec. 8 Trees: Maximum likelihood   Lecture notes
    		   
      Tues.
    Dec. 20    		   Final Exam:   1pm - 4pm,   Location: PH 125C
    		 This exam is closed book. You may bring two pages (or one page, front and back) of your own notes. Study questions  




    Return to course homepage
    Last modified: October 17, 2011.
    Maintained by Dannie Durand (durand@cs.cmu.edu).