Instructor: Shaojie Zhang
Lectures: Tu/Th 4:305:45 pm ENGR 0383
Office hours: Tu/Th 2:303: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. Graphbased clustering 17. Heuristic algorithms
Textbook:
Assignments: We will have 4 takehome assignments.
Grading: Assignments (50%), Midterm exam (20%), Final exam (25%), Attendance (5%).
Topics and Tentative Agenda:
Week  Date  Topic  Slides  Notes 

1  08/26  Introduction to algorithm  
08/28  Exact string matching  Dan 2.3, Dan 1.4  
2  09/02  Zvalue, Suffix trees Assignment 1 (Due 09/16)  Dan 1.4, Dan 6  
09/04  Suffix trees  Dan 6 Suffix 

3  09/09  Mismatch tree  CMB 8.6 Mitra 

09/11  Dynamic Programming  CMB CMB 6.2 and 6.3 MyersMiller algorithm 

4  09/16  DP Applications: RNA folding, complicated parameters  mfold  
09/18  DP Applications: RNA alignments with guiding tree Assignment 2 (Due 10/09)  Paper_1 Paper_2 

5  09/23  DP Applications: Pseudoknotted RNA alignments  pseudoknot  
09/25  DP Applications: RNA folding, a different formulation  RNAscf  
6  09/30  DP Applications: Spliced sequence alignment  CMB 9.4  
10/02  NPhard problem and multiple sequence alignment  
7  10/07  Algorithmic problems related to phylogenetic trees1  
10/09  Algorithmic problems related to phylogenetic trees2 (perfect phylogeny)  See above  
8  10/14  Algorithmic problems related to phylogenetic trees3 (SNPs)  See above  PPH 
10/16  Midterm Exam (takehome)  
9  10/21  Integer Programming Assignment 3 (Due 11/04)  CMB 6.11 Simplex algorithm 

10/23  Integer Programming applications  
10  10/28  De Bruijn graph and Eulerian graph1  CMB 5  
10/30  De Bruijn graph and Eulerian graph2 (fragment assembly)  See above  CMB 5  
11  11/04  Genome rearrangements and breakpoint graph1  CMB 10  
11/06  Genome rearrangements and breakpoint graph2 Assignment 4 (Due 11/25)  See above  CMB 10  
12  11/11  No Class (Veterans Day)  
11/13  Genome rearrangements and breakpoint graph3  
13  11/18  Computational Proteomics (Spectrum Graphs and Spectral Alignment)1  CMB 11  
11/20  Computational Proteomics (Spectrum Graphs and Spectral Alignment)2  See above  CMB 11  
14  11/25  Computational Proteomics (Spectrum Graphs and Spectral Alignment)3  See above  CMB 11 
11/27  No Class (Thanksgving Day)  
15  12/02  Computational Proteomics (Spectrum Graphs and Spectral Alignment)4  See above  CMB 11 
12/04  Review 
Research:
We are always looking for motivated students. If you are looking for
research projects, please get in touch.