CMSC 858L: Graphs and Networks in Computational Biology


This course surveys 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. This makes up about 2/3 of the class.

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. This makes up about 1/3 of the class.

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

No prior knowledge of biology is required.


Policies and Grading

Time: Tue. & Thu. at 9:30-10:45pm in room CSI 2118. See Testudo Listing

Office hours: 2:30 - 3:30 Tue. or by appointment.

Professor: Carl Kingsford; Office: CBCB 3113 Biomolecular Sciences Building (#296); Phone: 301-405-7395; Email: carlk AT

Web site:

Grades. Grades will be based on midterm (25%), final (30%), homeworks and quizzes (15%), a project and its presentation (25%), and participation (5%). Quizes will be announced 1 week in advance.

Project. Details about the project can be found here

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.

Academic honesty. The course follows the University's Academic Honor code.

Subject to change. The terms of this syllabus are subject to change.


Slides for the lectures can be found here.

Topics and Papers

Introduction (4 classes)

Basic relevant biology; experimental techniques for predicting interactions; Cytoscape; databases; graph algorithm libraries; network topological properties; phylogenetic profiles, mutual information.

Quiz #1: Tuesday, Feb. 10th on the above 5 papers.

Function Prediction from Interaction Networks (7 classes)

Multiway cut; integer programming; functional flow; graph summarization; notions of network distance; modularity; Kernighan-Lin partitioning heuristic; spectral partitioning for modularity; VI-CUT; MCL; MCODE; dense-subgraph detection.

Quiz #2: Tuesday, Mar. 3th on the above 5 papers.

Other papers of interest:

Network Searching and Alignments (5 classes)

PathBLAST; functional orthologs; PageRank-like algorithms; GRAEMLIN; speeding-up searches: color-coding.

Suggested Reading:

All of the following papers are tentative and will be finalized as we get to them.

Random Models of Biological Networks (3 classes)

Duplication model; small-world / preferential attachment models; Watts-Strogatz; evolving modularity; generating random graphs of a given degree distribution; graph motif-finding.

Dynamic Networks (1 class)

Other Graph Algorithms in Computational Biology (4 classes)

Side-chain packing (1 class), hardness via PCP theorem (1 class), semidefinite programming (1 class); phylogenetic trees & reassortment detection (1 class);

Background and Resources





Page created on Jan. 25, 2009. Valid HTML 4.01 Transitional