Schedule
Weekly topics covered and references for further reading will be posted here.
Week 1
(Jan 10 - Jan 12)
(i) basics of molecular biology, high-throughput sequencing, big-data challenges, (ii) dynamic range-minimum queries
MBCT Chapter 1, Chapter 3
Week 2
(Jan 15 - Jan 19)
(i) bitvector rank and select operations, (ii) exact matching, Z- algorithm, (ii) k-mer index, (iii) suffix array
Gusfield Chapter 1, MBCT Chapter 8, Manber and Myers 1993
Week 3
(Jan 22 - Jan 24)
(i) suffix array construction using prefix doubling, (ii) suffix tree
Gusfield Chapter 5
Week 4
(Jan 29 - Jan 31)
(i) LCP array, (ii) building suffix tree from suffix array, (iii) generalized suffix trees, (iv) applications of suffix trees
Kasai LCP construction algorithm, MBCT Theorem 8.15, Gusfield Chapter 7
Week 5
(Feb 5 - Feb 7)
(i) Burrows-Wheeler transform, (ii) FM-Index
MCBT 9.1, 9.2
Week 6
(Feb 14 - Feb 16)
(i) Repetitive DNA sequences (ii) Linear-time algorithm to compute maximal repeats
Gusfield 7.11.1, 7.12, 7.12.1
Week 7
(Feb 19 - Feb 23)
(i) Mid-term exam, (ii) Approximate matching, edit distance, (iii) Semi-global alignment
Gusfield 11.2, 11.3, 11.6, MBCT 6.1
Week 8
(Feb 26 - Mar 1)
(i) Discuss tentative project topics, (ii) Local alignment, (iii) Affine gap cost, (iv) Heuristic algorithms for approximate matching
Gusfield 11.7, 11.8, Aluru Chapter 15
Week 9
(Mar 4-Mar 4)
(i) Discuss mid-term exam questions, (ii) Sub-quadratic co-linear chaining algorithms
Aluru Chapter 15
Week 10
(Mar 11-Mar 15)
(i) Guest lecture by Jim Shaw, (ii) Genome assembly, (iii) Lander-Waterman statistics for shotgun sequencing (iii) Shortest common superstring, Greedy algorithm
Glenn Tesler's slides, Gusfield 16.15,16.17, Theorem 2 in [Bresler et al. 2013]
Week 11
(Mar 18-Mar 22)
(i) Assembly graphs, (ii) How to translate a biology question to a computer science question? (iii) Haplotype phasing
Rayan Chikhi's tutorial, Medvedev 2019, MBCT 14.3
Week 12
(Mar 25-Mar 27)
(i) Haplotype phasing (FPT algorithm), (ii) LZ text compression algorithm
MBCT 12-12.1
Week 13
(Apr 1-Apr 10)
(i) Project presentations