Fall 2011, CAP 6515: Algorithms in Computational Biology

Instructor: Shaojie Zhang

Lectures: T/Th 4:30-5:45 pm ENGR 286

Office hours: T/Th 10:30 am -11:30 pm and 3:30 - 4:30 pm, HEC 311

Syllabus: The course will concentrate on computer science aspects of computational molecular biology and will emphasize the recent advances and open problems in the area.

The computational techniques will include algorithms, graph theory, combinatorics, machine learning, etc. Many important bioinformatics topics will be used as examples to illustrate how the formulation and solution of a computer science problem can help to answer a biological question.

This course is designed for computer science graduate students. No biology knowledge is required.

Graduate students with either biology or physical/computer science backgrounds who have taken a fundamental bioinformatics course are also welcome to take this course.

Preliminary topics to be covered:
1. Introduction to algorithms
2. Exact string matching, Data structure: Suffix tree
3. Suffix tree: applications
4. Mismatch tree and the motif finding problem
5. Breaking problems down: dynamic programming
6. Combinatorial search: intractable problems
7. Integer programming; Reductions
8. Graph algorithms: trees
9. Haplotyping via perfect phylogeny
10. Comparing trees
11. De Bruijn graph; Eulerian graphs
12. Minimum Spanning trees; Shortest paths
13. Matching problems; Network flow
14. Breakpoint graph
15. Set cover and set packing
16. Graph-based clustering
17. Heuristic algorithms

Reference Textbooks:

Assignments: We will have 4 take-home assignments.

Grading: Assignments (40%), Midterm exam (25%), Final exam (25%), Attendance (10%).

Topics and Tentative Agenda:

Week	Date	Topic	Slides	Notes
1	08/23, 08/25	Introduction to algorithm	PDF
	08/25, 08/30	Exact string matching	PDF	Dan 2.3, Dan 1.4 KMP
2	08/30, 09/01	Z-value, Suffix trees	PDF Assignment 1 (Due 09/15)	Dan 1.4, Dan 6 Circular Pattern Matching (suggested by Arup)
3	09/06,09/08	Suffix trees	PDF	Dan 6 Suffix
4	09/13	Dynamic Programming	PDF	CMB CMB 6.2 and 6.3 Myers-Miller algorithm
	09/15	DP Applications: RNA folding, complicated parameters	PDF	mfold Zuker-Sankoff(1984)
5	09/20	DP Applications: RNA alignments with guiding tree	PDF Assignment 2 (Due 10/04)	Paper_1 Paper_2
	09/22	DP Applications: Pseudoknotted RNA alignments	PDF	pseudoknot
6	09/27	DP Applications: RNA folding, a different formulation	PDF	RNAscf
	09/29	DP Applications: Spliced sequence alignment	PDF	CMB 9.4
7	10/04	NP-hard problem and multiple sequence alignment	PDF
	10/06	Algorithmic problems related to phylogenetic trees-1	PDF
8	10/11	Algorithmic problems related to phylogenetic trees-2 (Fitch Algorithm)	See above
	10/13	Mid-term Exam (take-home)
9	10/18	Algorithmic problems related to phylogenetic trees-4 (perfect phylogeny)	See above
	10/20	Algorithmic problems related to phylogenetic trees-5 (SNP)	See above	PPH
10	10/25	Algorithmic problems related to phylogenetic trees-5 (SNP and Haplotyping)	See above Assignment #3 (Due 11/08)	PPH
	10/27	De Bruijn graph and Eulerian graph-1	PDF	CMB 5
11	11/01 No class on 11/03	De Bruijn graph and Eulerian graph-2 (fragment assembly)	See above	CMB 5
12	11/08	Genome rearrangements and breakpoint graph-1	PDF	CMB 10
	11/10	Genome rearrangements and breakpoint graph-2	See above Assignment 4 (Due 11/29)	CMB 10
13	11/15	Genome rearrangements and cancer genomics Linear Programming and Interger Programming	PDF PDF (LP and ILP)
	11/17	Computational Proteomics (Spectrum Graphs and Spectral Alignment)-1	PDF	CMB 11
14	11/22	Computational Proteomics (Spectrum Graphs and Spectral Alignment)-2	PDF	CMB 11
	11/24	No Class (Thanksgiving Day)
15	11/29	Computational Proteomics (Spectrum Graphs and Spectral Alignment)-3	See above	CMB 11
	12/01	Computational Proteomics (Spectrum Graphs and Spectral Alignment)-4	See above	CMB 11
16	12/06	Take-home Final Exam Due

Research:
We are always looking for motivated students. If you are looking for research projects, please get in touch.