UMD
CMSC 858L: Network Algorithms for Biology
(formerly Graphs and Networks in Computational Biology)

Overview

This course covers recent research on graph algorithms for the computational analysis of biological networks, such as protein-protein and protein-DNA interaction graphs.

No prior knowledge of biology is required. Necessary concepts from biology will be reviewed as needed. Computationally-inclined biology graduate students are encouraged to take the class as well. Some basic computer science knowledge is assumed but an effort is made for the class to be self-contained.

The course is a Ph.D. and MS qualifying course in Alg/Thy. It is a MS comp course as well, where the MS comp grade will be derived from grades on the Midterm and Final.

The course covers a wide range of algorithmic techniques and tools, with the goal that when you are faced with some problem in the future, you will have seen many techniques that might be applicable. The course is useful even for people who will not focus on computational biology. Topics we may cover include:

  • Graph clustering and partitioning
  • Clique finding
  • Enumerating maximal bicliques
  • Minimum multiway cuts
  • Subgraph isomorphmism
  • Random walks, markov random fields
  • PageRank-like algorithms
  • Modularity
  • Graph coloring
  • Constraints statistifaction
  • PCP theorem to prove inapproximability
  • Linear, integer, and semidefinite programming
  • Entropy, mutual information
  • Color coding to speed up dynamic programming
  • Random graph growth processes
  • Spectral partitioning

Biological problems considered include predicting protein function from protein interaction networks, comparing interaction networks from multiple organisms, finding common network patterns, inferring interactions between proteins, modeling signalling pathways, 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.

Announcements

Lectures

Papers

A selection of papers that we may read as part of the class can be found here.

Topics

A reasonable collection of topics that appeared the last time the class was taught is given below. Some topics are likely to change

Introduction (4 classes)

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

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.

Network Searching and Alignments (5 classes)

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

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), linear programming, semidefinite programming (1 class); phylogenetic trees & reassortment detection (1 class);

Policies and Grading

Time: Mon. & Wed. at 3:30-4:45pm in room CSI 3120. See Testudo Listing

Office hours: 2:30 - 3:30 Tuesday in AVW 3223, or by appointment.

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

Web site: http://www.cs.umd.edu/class/fall2009/cmsc858l/

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. Project guidelines are posted 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.

Background and Resources

Background:

Databases:

Code:

Visualization:


Page created on Jul. 15, 2009. Valid HTML 4.01 Transitional