Teaching Materials

You are free to use these materials. Feel free to email me to tell me how you are using them, or to ask for a copy of the original Keynote files. You can also browse all course videos on my YouTube channel.

🎬 123 videos · 35+ hours 📄 ~150 slide decks 📓 42 notebooks 🎓 1 full Coursera course

Click a course title to expand.

Algorithms for DNA Sequencing · offered through Coursera exact matching · Boyer-Moore · indexing · BWT · FM-index · alignment · assembly · Markov chains · HMMs

▶

🎬 55 videos · ~7 hours 📄 24 slide decks 📓 39 notebooks 🎓 full Coursera course

Introductory

Strings and matching

Strings and exact matching
- Notebook: Strings (Python, Py+Colab, Go)
- Notebook: Naive exact matching (Python, Py+Colab, Go)
Boyer-Moore
- Notebook: Z algorithm (Python, Py+Colab, Go)
- Notebook: Boyer-Moore (Python, Py+Colab, Go)
Approximate matching
- Notebook: Naive approximate (Python, Py+Colab, Go)
- Notebook: Pigeonhole principle (Python, Py+Colab, Go)

Indexing

Indexing with substrings
- Notebook: Substring indexes (Python, Py+Colab, Go)
- Notebook: Grouped and ordered indexes (Python, Py+Colab, Go)
Tries and suffix tries
- Notebook: Trie map (Python, Py+Colab, Go)
- Notebook: Suffix trie (Python, Py+Colab, Go)
Suffix trees
- Notebook: Suffix tree (Python, Py+Colab, Go)
Suffix arrays
- Notebook: Binary search (Python, Py+Colab, Go)
- Notebook: Suffix-array binary search (Python, Py+Colab)
- Notebook: Longest common prefix (Python, Py+Colab)
- Notebook: From suffix tree to LCP/suffix array (Python, Py+Colab)
Burrows-Wheeler Transform and FM Index
- Notebook: Burrows-Wheeler Transform (Python, Py+Colab)
- Notebook: Reversing the BWT (Python, Py+Colab)
- Notebook: FM Index (Python, Py+Colab)

Sequence alignment

Dynamic programming and edit distance
- Notebook: Hamming distance, edit distance, dynamic programming (Python, Py+Colab)
- Notebook: Approximate matching dynamic programming (Python, Py+Colab)
Global alignment
- Notebook: Global alignment (Python, Py+Colab)
Local alignment
- Notebook: Local alignment (Python, Py+Colab)
Dynamic programming in less time and space
Index-assisted approximate matching and read alignment
- Notebook: Index-assisted pigeonhole principle (Python, Py+Colab)

Assembly

Assembly & Shortest Common Superstring
- Notebook: Brute-force SCS (Python, Py+Colab)
- Notebook: Finding overlaps (Python, Py+Colab)
- Notebook: Greedy SCS (Python, Py+Colab)
De Bruijn Graph Assembly
- Notebook: Simple De Bruijn graph (Python, Py+Colab)
- Notebook: De Bruijn graph (Python, Py+Colab)
In practice: Overlap Layout Consensus
In practice: De Bruijn Graphs
- Notebook: Error correction (Python, Py+Colab)
In practice: Scaffolding

Sequence models and classification

Sequence modeling
Markov chains
- Notebook: Markov chains (Python, Py+Colab)
- Notebook: High-order Markov chains (Python, Py+Colab)
Hidden Markov models
- Notebook: Hidden Markov Model (Python, Py+Colab)
Genes and gene finding

File formats

Notebook: FASTA (Python, Py+Colab)
Notebook: FASTQ (Python, Py+Colab)
Notebook: SAM (Python, Py+Colab)

Miscellaneous

Notebook: Radix sort (Python, Py+Colab)
Notebook: Min hashing (Python, Py+Colab)
Notebook: Minimizers (Python, Py+Colab)
Notebook: RepeatMasker (Python, Py+Colab)

Burrows-Wheeler Indexing entropy · BWT · FM-index · bitvectors · wavelet trees · Wheeler graphs · r-index · run-length encoding

▶

🎬 27 videos · ~12 hours 📄 27 slide decks

Burrows-Wheeler Transform

Bitvectors

Wavelet Trees

FM Index

Wheeler Graphs

BWT for Repetitive Texts (r-index)

Move Structure

Suffix Indexing tries · suffix tries · suffix trees · suffix links · matching statistics · suffix arrays · LCP arrays

▶

🎬 15 videos · ~5 hours 📄 15 slide decks

Tries and Suffix Tries

Tries (YouTube)
Suffix Tries
- Introduction (YouTube)
- Size (YouTube)

Suffix Trees

Suffix Arrays

Sketching and Randomized Data Structures hash tables · bloom filters · universal hashing · cardinality estimation · MinHash · Jaccard similarity · CountMin sketch

▶

🎬 16 videos · ~7.5 hours 📄 10 slide decks 📓 3 notebooks

Hash Tables and Probability (YouTube part 1, part 2)
Hashes and Randomness (YouTube)
Bloom filters (YouTube part 1, part 2)
- Notebook: Shakespeare containment queries (Py+Colab)
Coupon Collector and More Bloom Filters (YouTube)
- Notebook: Coupon collector simulations (Py+Colab)
Randomness and Independence (YouTube)
Universal hashing
- Use in Hash Table Proof (YouTube)
- ax + b mod p family (YouTube)
Cardinality
- Hat problem (YouTube)
- Proof and kth-Minimum Value (YouTube)
Similarity and MinHash (YouTube)
- Notebook: Shakespeare MinHash (Py+Colab)
Markov’s Inequality (YouTube)
CountMin sketch
- Definition and Point Query (YouTube)
- Proving Error Bound (YouTube)
- Conservative Update and Matrix Nature (YouTube)

Sequence Modeling probability · Markov assumption · Markov chains · Hidden Markov Models · Viterbi decoding · CpG islands · gene finding

▶

🎬 10 videos · ~4 hours 📄 10 slide decks

Covers the foundations of probabilistic sequence modeling with applications to computational biology: the Markov assumption, Markov chains, and Hidden Markov Models, with applications to CpG island finding and gene finding.

C and C++ Programming compilation · types · pointers · memory · stack/heap · structs · OOP · templates · STL · inheritance · polymorphism

▶

📄 64 slide decks — source on GitHub