(i) basics of molecular biology, high-throughput sequencing, big-data challenges, (ii) dynamic range-minimum queries

(i) Bitvector rank and select queries, (ii) exact matching, Z-algorithm (iii) k-mer index, (iv) Suffix-array

(i) k-mer index (ii) Suffix-array (iii) Construction of suffix arrays (iv) Prefix-doubling approach for suffix array construction

(i) Suffix tries (ii) Suffix trees (iii) LCP array (iv) Kasai's algorithm for constructing LCP arrays

(i) Generalised suffix trees (ii) Applications
Highlight: All-pairs longest suffix-prefix overlap problem

(i) Burrows-Wheeler transform (ii) LF-Mapping (iii) FM-index

(i) Demo: Burrows-Wheeler transform, IGV alignment visualisation (ii) Mid-term examination (iii) Approximate matching (iv) Edit distance

(i) Project topics (ii) Mid-term examination solutions (iii) Score-based approximate matching (iv) Global alignment (v) Approximate occurrence of a pattern in a text (vi) Local alignment

(i) Affine gap costs in approximate alignment (ii) Statistical significance of alignments  (iii) Karlin-Altschul theory (iv) Maximal Unique Matches

(i) Co-linear chaining (ii) Sub-quadratic algorithms for finding best scoring chain (iii) Co-linear chaining with L1 gap cost

(i) Genome assembly (ii) Lander-Waterman statistics for shotgun sequencing (iii) Shortest common superstring (iv) Greedy algorithm for SCS (v) Runtime analysis, approximation factor, and feasibility of Greedy SCS

(i) de Bruijn Graphs (ii) Genome assembly using de Bruijn graphs (iii) Project presentations 

Project presentations