| Lecture slides |
Recommended reading |
| A brief introduction to molecular biology concepts and algorithmic problems in computational biology. Week 1, Lectures 1-2 A brief introduction to computational complexity and algorithm design techniques Week 1, Lecture 3 |
EBI's Introduction to Biology JGI's Introduction to Genomics Chapter 3 of the textbook Chapter 2 of the text book |
| DNA mapping & motif search Week 2, Lectures 1-2 Exact sequence search algorithms Week 2, Lecture 3 |
Chapter 4 of the text book |
| Rabin-Karp algorithm, finite automata, pattern matching, suffix trees Week 3, Lectures 1-2 Shift-and algorithm, Aho-Corasick algorithm, suffix arrays Week 3, Lecture 3 |
Chapter 9 of the text book |
| Elements of dynamic programming, Manhattan tourist problem, introduction to sequence alignment Week 4, Lectures 1-2 Global alignment, local alignment, affine gap penalties Week 4, Lecture 3 |
Chapter 6 of the text book |
| Approximate string matching, divide and conquer algorithms, Four-Russians trick Week 5, Lectures 1-2 Week 5, Lecture 3: Quiz 2 |
Chapters 7 and 9 of the text book |
| Multiple sequence alignment Week 6, Lectures 1-2 Week 6, Lecture 3 canceled due to holidays |
Chapter 6 of the text book |
| Gene finding Week 7, Lectures 1-2 Heuristic sequence search Week 7, Lecture 3 |
Chapter 6 of the text book |
| Spaced seeds for heuristic spaced seeds, introduction to Hidden Markov Models Week 8, Lectures 1-2 Hidden Markov Models, Viterbi algorithm, Forward/Backward algorithm, profile HMMs Week 8, Lecture 3 |
Chapters 9 and 11 of the text book |
| Week 9, Lectures 1-2 are canceled Hidden Markov Models, Viterbi training, Baum-Welch algorithm Week 9, Lecture 3 |
Chapter 11 of the text book |
| Phylogenetic tree construction Week 10, Lectures 1-2 Week 10, Lecture 3 |
Chapter 10 of the text book |
| Clustering algorithms Week 11, Lectures 1-2 CAST algorithm, introduction to genome rearrangements Week 11, Lecture 3 |
Chapter 10 of the text book |
| Genome rearrangements, sorting by reversal Week 12, Lectures 1-2 Week 12, Quiz 4 |
Chapter 5 of the text book |
| RNA folding Week 13, Lectures 1-2 Week 13, Lecture 3 is canceled. |