main page — CS 594 Algorithms of Bioinformatics
Unit 7: Googling Genomes
Material
- slides
- Video 7-1 (2026-01-15):
Range-minimum queries
- Video 7-2 (2026-01-15):
RMQ via sparse tables
- Video 7-3 (2026-01-22):
Cartesian trees
- Video 7-4 (2026-01-22):
String matching in enhanced suffix arrays
- Video 7-5 (2026-01-22):
The Burrows-Wheeler transform
- Video 7-6 (2026-01-22):
The Inverse BWT
- Video 7-7 (2026-01-22):
Random access in BWT-compressed texts
- Video 7-8 (2026-01-22):
String matching in BWT-compressed texts, backward search, FM Index
Further sources
The RMQ presentation is based on own work. It takes inspiration from the following paper on the related level-ancestor problem:
A more detailed exposition (with slightly different codes for the lookup table) appears here:
- Ohlebusch: Bioinformatics algorithms (2013) Oldenbusch Verlag
The presentation of the Burrows-Wheeler, forward and backward search is my own; apart from Ohlebusch’s book, a slightly different exposition and many refinements are given in:
- Navarro: Compact Data Structures: A Practical Approach (2016), Cambridge University Press