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