CMSC 858L: Network Algorithms for Biology(formerly Graphs and Networks in Computational Biology)
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:
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.
A reasonable collection of topics that appeared the last time the class was taught is given below. Some topics are likely to change
Basic relevant biology; experimental techniques for predicting interactions; Cytoscape; databases; graph algorithm libraries; network topological properties; phylogenetic profiles, mutual information.
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.
PathBLAST; functional orthologs; PageRank-like algorithms; GRAEMLIN; speeding-up searches: color-coding.
Duplication model; small-world / preferential attachment models; Watts-Strogatz; evolving modularity; generating random graphs of a given degree distribution; graph motif-finding.
Side-chain packing (1 class), hardness via PCP theorem (1 class), linear programming, semidefinite programming (1 class); phylogenetic trees & reassortment detection (1 class);
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.
Page created on Jul. 15, 2009.