CPS 260 (BGT 204): Algorithms for Computational Biology

Instructor: Kamesh Munagala
   Fall Semester, 2005

This course will cover algorithmic techniques in computational molecular biology at a graduate level. Topics include dynamic programming, sequencing algorithms, alignments, scoring matrices, pattern matching, BLAST, unsupervised and supervised learning, SVD, phylogeny tree reconstruction, hidden Markov models, and protein structure. You need CPS130 or equivalent as prerequisite. The course includes a project which involves paper reading and/or original research on any topic of your choice.

Assignments:
9/13:  Homework 1   (Due 9/28)
9/29:  Homework 2   (Due 10/12)
11/9:  Homework 3   (Due  11/21)

Administration: 
Lectures:           Wed 18:00-19:15   (D106)
                          Fri    14:50-16:05   (D106)
Office Hours:    (Kamesh)       Thu  13:30-15:30   (D205)
                          (Bei Wang)    Fri   13:00-14:50   (D110)
Grading: Homeworks (30%).  Project (20%). Midterm (20%), End-term (30%).


Lect.  Date  Topics  Handouts  Reading 
1,2 Aug. 31
Sep. 2
Basic Molecular Biology

[Jon, Ch 3]
[MBC]
3
Sep. 7
The Human Genome Project

[Pev, Ch 4]
[Gus, Ch 16]
4
Sep. 9
Graph Algorithms in Sequencing:
SBH and Eulerian Paths

[Jon, Ch 8]
[Gus, Ch 16]
5
Sep. 14
De-novo Peptide Sequencing:
Longest Paths and Dynamic Programming
HW1
(Due 9/28)
[Jon, Ch 8]
[Lec5]
6
Sep. 16
Sequence Alignment: Edit distance, LCS
PAM and BLOSUM Scoring Matrices

[Jon, Ch 6]
[Gus, Ch 15]
7
Sep. 21
Local Alignments: Smith Waterman Algorithm
Gap Penalties

[Jon, Ch 6]

8
Sep. 23
Space Efficient Alignment Algorithms
Fast LCS using Table Lookup

[Jon, Ch 7]
9
Sep. 28
Exact Pattern Matching: KMP Algorithm,
[Jon, Ch 7]
10
Sep. 30
Keyword Trees, Aho-Corasick Algorithm
(Due 10/12) [Jon, Ch. 9]
[Gus, Ch 3]
11
Oct. 5
Database Search: FASTA and BLAST

[Gus, Ch 15]

12

Oct. 7
Clustering Basics
Hierarchical Clustering
Multiple Sequence Alignment: CLUSTAL


[Jon, Ch 6,10]
13
Oct. 12
Center-based Clustering

[Jon, Ch 10]
14
Oct. 14
Clustering via Cliques

[Lec14]
15
Oct. 19
MIDTERM


16
Oct. 21
Singular Value Decomposition

[Lec16]
17
Oct. 26
Evolutionary Trees and Ultrametrics
Additive distance trees

[Jon, Ch 10]
18
Oct. 28
Perfect Phylogeny Problem (Lecture by Bei Wang)
[Gus, Ch 17]
19
Nov. 2
Small Parsimony Problem
Nearest Neighbor Interchange

[Jon, Ch 10]
20
Nov. 4
Hidden Markov Models: Basics

[Jon, Ch 11]
21
Nov. 9
Forward and Backward (Viterbi) Algorithms
HW3
(Due 11/21)
[Jon, Ch 11]
22
Nov. 11
Classification Problems: Linear Classifiers


23
Nov. 16
Feature Selection in Gene Expression Data


24
Nov. 18

Protein Structure
(Guest lectures by Herbert Edelsbrunner)


25
Nov. 30
FINAL EXAM


26
Dec. 2
Final Project Presentations




Course Materials:

[Jon]  An Introduction to Bioinformatics Algorithms  by Neil C. Jones, Pavel A. Pevzner
[Pev] Computational Molecular Biology: An Algorithmic Approach  by Pavel A. Pevzner
[Gus] Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology by Dan Gusfield
[MBC] Molecular Biology of the Cell  online (for access to the contents of any section, simply cut-paste the title of the section into the search box).
[Lec5]   A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry
[Lec14] Clustering Gene Expression Patterns
[Lec16] Singular Value Decomposition
[Lec19] The neighbor-joining method: A new method for reconstructing phylogenetic trees