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.

Full courses online

Algorithms for DNA Sequencing

• Full course on Coursera
• Lecture videos on YouTube (55 lectures, about 7 minutes each)
• Lecture notes on GitHub
• Jupyter notebooks on GitHub

Lecture notes

Computational Genomics

Introductory

• What are Genomics and Computational Genomics?
• DNA sequencing

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)

Suffix Indexing

Notes added July, 2023

YouTube playlist added summer, 2022 and updated summer, 2023

• Tries (YouTube)
• Suffix Tries
  • Introduction (YouTube)
  • Size (YouTube)
• Suffix Trees
  • Definition and Size (YouTube)
  • Building (YouTube)
  • Basic Queries (YouTube)
  • Suffix Links (YouTube)
  • Matching Statistics: Definition (YouTube)
  • Matching Statistics on the Suffix Tree (YouTube)
• Suffix Arrays
  • Definition and Size (YouTube)
  • Basic Queries (YouTube)
  • Building (YouTube)
  • Min LCP skipping (YouTube)
  • Maximum skipping (YouTube)
  • The Suffix Tree is Hiding (YouTube)

Burrows-Wheeler Indexing

Notes added May, 2020

YouTube playlist added July 2020, updated in summer 2022 and 2023

• Intro: Indexing (YouTube)
• Entropy and Coding (YouTube)
• High Order Empirical Entropy (YouTube)
• Burrows-Wheeler Transform
  • Intro and Compression Boosting (YouTube)
  • Reversing the BWT (YouTube)
• Bitvectors
  • Bitvectors, Rank, Seclect, Access (YouTube)
  • Jacobson’s Rank (YouTube)
  • Clark’s Select (YouTube)
• Wavelet Trees
  • Definition and Queries (YouTube)
  • Space, Time, Huffman Shape (YouTube)
• FM Index:
  • Efficient Reversal (YouTube)
  • Efficient Matching (YouTube)
• Wheeler Graphs
  • Substrings to Paths (YouTube)
  • BW Order for Graphs (YouTube)
  • Definition (YouTube)
  • Consecutivity (YouTube)
  • Data Structures and Matching (YouTube)
• BWT for Repetitive Texts (r-index)
  • Runs (YouTube)
  • Run-Length FM Index (YouTube)
  • Toehold Lemma Setup (YouTube)

Sketching and Randomized Data Structures

Notes added May, 2020

YouTube playlist added July, 2020, 16 videos

• 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)

C and C++ Programming

Last updated May 9, 2020

See GitHub repo with original markdown and compilation script

• Course goals
• Course conventions
• Stages of compilation and Hello, World
• Variables, types, operators
• Printing messages
• Decisions
• Arrays
• Characters and Strings
• Reading input
• Command line arguments
• Assertions
• Math
• Compiling and Linking
• Functions
• Program structure
• Makefiles
• Memory
• Pointers
• Pointers and Arrays
• Lifetime and Scope
• Stack and Heap
• Dynamic memory allocation
• Debugging with valgrind
• Debugging with gdb
• Structures
• Beyond 1D arrays
• Binary input/output
• Numeric types
• Type casting and Promotion
• Bitwise operators
• Linked lists

C++ programming

• C++ intro
• C++ I/O and Namespaces
• C++ strings
• Standard Template Library (STL)
• STL Vector and Iterators
• STL Map
• More about Iterators
• STL Pairs and Tuples
• References
• Classes
• Constructors
• New and Delete
• Non-default constructors
• Destructors
• Passing by Reference
• Inheritance
• Polymorphism
• Virtual Destructors
• Overloading
• Enumerations
• Static Members
• Object Oriented Design Principles
• Building Strings with stringstream
• File I/O with fstream
• Exceptions
• The Rule of 3
• Template Functions
• Template Classes
• Abstract Classes
• Writing a Container Class
• Auto Type
• ranged_for loops
• override keyword