CMSC 701: Computational Genomics (Fall 2014)

Lecture Notes




Tuesday, September 2

Introduction to class

Lecture 1

Thursday, September 4

Exact matching: intro & KMP algorithm

Tuesday, September 9

Exact matching: Boyer-Moore

Thursday, September 11

Exact matching: multiple pattern Aho-Corasick

Tuesday, September 16

Exact matching: automata

Thursday, September 18

Suffix trees: properties

Tuesday, September 23

Suffix trees: construction with Ukkonen's algorithm

Thursday, September 25

Suffix arrays

Tuesday, September 30

BWT, compressed suffix arrays

Thursday, October 2

Inexact alignment: dynamic programming

Tuesday, October 7

Inexact alignment: dynamic programming variants, RNA structure

Thursday, October 9

Speed-ups/parallel algorithms

Tuesday, October 14

Alignment statistics

By Dr. Stephen Altschul
Lecture slides

Thursday, October 16

Alignment statistics

By Dr. Stephen Altschul
Lecture slides

Tuesday, October 21


Thursday, October 23

Alignment heuristics

Tuesday, October 28

Alignment heuristics/spaced seeds

Thursday, October 30

Chaining algorithms

Tuesday, November 4

Multiple sequence alignment

Thursday, November 6

Multiple sequence alignment

Tuesday, November 11

Motif finding by Stephen Altschul

Gibbs Sampling

Local Multiple Sequence alignment

Thursday, November 13

Multiple alignment scoring based on Dirichlet mixtures

Dirichlet mixtures

Tuesday, November 18

Probabilistic alignment, markov models

Thursday, November 20

Sequence clustering/Phylogeny

Tuesday, November 25

Sequence clustering/Phylogeny

Thursday, November 27

Thanksgiving, no class

Tuesday, December 2

Sequence assembly

Thursday, December 4

Sequence assembly

Tuesday, December 9


Thursday, December 11

Current research topics

Tuesday, December 16