UMD

CMSC 858L: Graphs and Networks in Computational Biology

Lectures

These lectures were given in CMSC 858L "Network Algorithms for Biology" graduate class in the Computer Science Department at the University of Maryland, College Park. Many of the algorithms are described in the papers listed here.

    Biological Background and Network Construction

  1. 1/27/09: Lecture 1: Introduction
  2. 1/29/09: Lecture 2: Experimental Methods: Yeast 2-hybrid
  3. 2/3/09: Lecture 3: Other experimental protocols (TAP-MS, SSL, ChIP-chip)
  4. 2/5/09: Lecture 4: In silico prediction of edges

    Function Prediction (esp. via graph partitioning)

  5. 2/10/09: Lecture 5: Function Prediction (min mulitway cut, integer programming, neighborhood, majority, functional flow)
  6. 2/12/09: Lecture 6: Graph Summarization (guest lecture by Saket Navlakha)
  7. 2/17/09: Lecture 7: Notions of Node Similarity; Modularity; Kernighan-Lin
  8. 2/19/09: Continued slides from 2/17/09.
  9. 2/24/09: Lecture 8: Entropy; variation of information; VI-CUT
  10. 2/26/09: Lecture 9: MCODE, RNSC, started MCL
  11. 3/3/09: Finished MCL (slides above), Quiz #2

    Network Alignment, Comparison, Searching

  12. 3/5/09: Lecture 10: PathBLAST
  13. 3/10/09: Lecture 11: Functional Orthologs (board lecture; unedited lecture notes)
  14. 3/12/09: Lecture 12: Color Coding (first 9 slides)
  15. 3/24/09: midterm
  16. 3/26/09: Color Coding (Lecture 12), continued (slides above)
  17. 3/31/09: Lecture 13: IsoRank Alignment, Graemlin

    Random Graphs, Network Motifs

  18. 4/2/09: Lecture 14: Random Graphs, Degree Distribution, Network Motifs
  19. 4/7/09: Lecture 15: Random Processes for Growing Graphs
  20. 4/9/09: Lecture 16: Finding motifs via symmetry breaking

    Other Graph Algorithms in Computational Biology

  21. 4/14/09: Lecture 17: Side-chain positioning
  22. 4/16/09: Lecture 18: PCP Theorem & hardness of approximating SCP (board lecture)
  23. 4/21/09: Lecture 19: SCP via Semidefinite Programming
  24. 4/23/09: Lecture 20: Dynamics of Regulatory Networks
  25. 4/28/09: Project work day
  26. 4/30/09: Lecture 21: Phylogenetic trees & Reassortment Detection
  27. 5/5/09: Project Presentation Day #1
  28. 5/7/09: Project Presentation Day #2
  29. 5/12/09: Lecture 22: Summary, Wrap-up, etc.