UMD

CMSC 858L: Graphs and Networks in Computational Biology

Eulerian Graph of a Genome This is a seminar course surveying recent research on computational analysis of biological networks, such as protein-protein and protein-DNA interaction graphs. Topics include predicting protein function from protein interaction networks, comparing interaction networks from multiple organisms, finding common network motifs, inferring missing edges, and visualizing biological graphs.

We will also cover some additional uses of graphs in modeling biological problems, including inferring trees and DAGs corresponding to an organism's evolutionary history, genome assembly using short reads, genome rearrangements, and protein side-chain optimization.

These topics illustrate practical application of (for example) Eulerian tours, minimum multiway cut, graph coloring, subgraph isomorphism, constraint satisfaction, graph layout, and clique finding.

Most of the class will consist of student presentations of recent papers. No prior knowledge of biology is required. In addition, biology graduate students interested in computational approaches are encouraged to attend.

Administrative Information

Time: Tue. & Thurs. at 3:30-4:45pm in room: CSI 2118
Professor: Carl Kingsford - 3113 Biomolecular Sciences Building (#296) - 301-405-7395 - carlk AT cs.umd.edu
Office hours: 2:30 - 3:30 Tue. in AVW 3223 (Phone: 5-6713)
Web site: http://www.cs.umd.edu/class/fall2007/cmsc858l/

Grading

You will present several papers to the class for discussion from the list of below. These presentations should be 25 minutes long and cover the methods in as much detail as possible. You should try to identify and discuss potential problems with the work.

You will do a class project in groups of 2.

Each project group will give a short (5 min) project proposal in the middle of the semester in order to get feedback. You will also give a longer (15-20 minutes) presentation on the results of your project and turn in a write up (of at most 5 pages + references and figures) at the end of the semester.

Grading: 60% presentations, 25% project, and 15% participation.

Schedule / Syllabus

DateTopic / PapersPresenter
8/30Introduction, graph problems Kingsford
9/4Experimental techniques Kingsford (PDF)
9/6Introduction continued Kingsford (PDF)
Annotating Function
9/11
  1. Vazquez et al. Global protein function prediction from protein-protein interaction networks. Nat. Biotechnol. 21:697-700, 2003.
  2. Spirin and Mirny. Protein complexes and functional modules in molecular networks. Proc. Natl Acad. Sci. USA 100:12123-12128, 2003.
Guillaume (PDF)
Sam A
9/13
  1. Karaoz et al. Whole-genome annotation by using evidence integration in functional-linkage networks. Proc. Natl Acad. Sci. USA 101:2888-2893, 2004.
  2. Nabieva et al. Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps. Bioinformatics 21(Suppl 1):i302-10, 2005.
Sergey (PDF)
Saket (PPT)
Comparing and searching interaction networks
9/18
  1. Kelley et al. Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc. Natl. Acad. Sci. USA 100:11394-11399, 2003.
  2. Bandyopadhyay et al. Systematic identification of functional orthologs based on protein network comparison. Genome Res. 16:428-435, 2006.
Adam (PPT)
Mike (PDF)
9/20
  1. Gandhi et al. Analysis of the human protein interactome and comparison with yeast, worm and fly interaction datasets. Nat. Genet. 38:285-293, 2006. [B]
  2. Singh et al. Pairwise global alignment of protein interaction networks by matching neighborhood topology. RECOMB 2007. [M]
Cole (PDF)
Guillaume (PDF)
9/25
  1. Dost et al. QNet: A tool for querying protein interaction networks. RECOMB 2007. [M]
  2. Pinter et al. Alignment of metabolic pathways. Bioinformatics 21(16):3401-3408, 2005.
Sergey (PDF)
Sam (PDF)
Random models of networks; finding network motifs
9/27
  1. Milo et al. Network motifs: simple building blocks of complex networks. Science 298:824-827, 2002.
  2. Grochow and Kellis. Network motif discovery using subgraph enumeration and symmetry-breaking. RECOMB 2007.
Saket (PPT)
Adam (PPT)
10/2
  1. Zhang et al. Motifs, themes and thematic maps of an integrated Saccharomyces cerevisiae interaction network. J Biology 4:6, 2005.
  2. Batada et al. Stratus not altocumulus: A new view of the yeast protein interaction network. PLoS Biol. 4:e317, 2006. [B]
Cole (PDF)
Sam (PDF)
10/4
  1. Newman. Modularity and community structure in networks. Proc. Natl. Acad Sci USA 103:8577-8582, 2006.
  2. Yu et al. The importance of bottlenecks in protein networks: correlation with gene essentiality and expression dynamics. PLoS Comp. Biol. 3:713-720, 2007.
Galileo (PDF)
Sam (PDF)
10/9
  1. Scott et al. Efficient algorithms for detecting signaling pathways in protein interaction networks. RECOMB 2005. [M]
  • Mini Review
Guillaume (PDF)
Kingsford (PDF)
Visualizing biological graphs
10/11
  1. Shannon et al. Cytoscape: A software environment for integrated models of biomolecular interaction networks. Genome Res. 13:2498-2504, 2003.
  2. Li and Kurata. A grid layout algorithm for automatic drawing of biochemical networks. Bioinformatics 21(9):2036-2042, 2005. [M]
Galileo (PDF)
Sergey (PDF)
10/16Project Proposals / Status
Predicting physical and functional interactions
10/18Generating Graphs of Given Degree Dist. Kingsford
10/23
  1. Jansen et al. A Bayesian networks approach for predicting protein-protein interactions from genomic data. Science 302:449-453, 2003.
  2. Troyanskaya et al. A Bayesian framework for combining heterogeneous data sources for gene function prediction (in Saccharomyces cerevisiae). Proc. Natl Acad. Sci. USA 100:8348-8353, 2003.
Galileo (PDF)
Adam (PPT)
10/25
  1. Yu et al. Predicting interactions in protein networks by completing defective cliques. Bioinformatics, 22(7):823-829, 2006.
  2. Srinivasan et al. Integrated protein interaction networks for 11 microbes. RECOMB 2006.
Saket (PPT)
Mike (PDF)
10/30
  1. Zhang et al. Predicting co-complexed protein pairs using genomic and proteomic data integration. BMC Bioinformatics 5, 2004.
  2. Singh et al. Struct2Net: integrating structure into protein-protein interaction networks. PSB 2006.
Cole
Mike (PDF)





Networks, Gene Expression, Dynamics
11/1 NO CLASS
11/6
  1. Luscombe et al. Genomic analysis of regulatory network dynamics reveals large topological changes. Nature 431:308-312, 2004. [B]
Kingsford
11/8
  1. Discussion of Wiggins Seminar
  2. Simple random graph proofs; Watts & Strogatz
Kingsford
Phylogenetic networks, reticulated evolution
11/13Phylogenetic treesKingsford
11/15
  1. Huson and Kloepper. Computing recombination networks from binary sequences. Bioinformatics 21(Suppl 2):ii159-ii165, 2005.
  2. Bryant and Moulton. NeighborNet: An agglomerative method for the construction of planar phylogenetic networks. WABI 2002.
Kingsford
Other
11/20Genome assemblyKingsford
11/27Genome rearrangementsKingsford
11/29Side-chain positioningKingsford
Projects
12/4Project Presentations
12/6Project Presentations
12/11Summary, Questions, Future DirectionsKingsford

Resources

Fine Print

Excused absences. Students claiming an excused absence must apply in writing and furnish documentary support (such as from a health care professional who treated the student) for any assertion that the absence qualifies as an excused absence. The support should explicitly indicate the dates or times the student was incapacitated due to illness. Self-documentation of illness is not itself sufficient support to excuse the absence. Absences for religious observances must be submitted in writing to the instructor within two weeks of the start of the semester. The instructor is not under obligation to offer a substitute assignment or to give a student a make-up assessment unless the failure to perform was due to an excused absence. An excused absence for an individual typically does not translate into an extension for team deliverables on a project.

Academic accommodations. Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.

Last modified 30 Aug 2007. Valid HTML 4.01 Transitional