Unit 7: Googling Genomes

Material

• slides

• lecture notes

• Video 7-1 (2026-01-15, 10:22): Range-minimum queries
  
• Video 7-2 (2026-01-15, 7:09): RMQ via sparse tables
  
• Video 7-3 (2026-01-22, 20:26): Cartesian trees
  
• Video 7-4 (2026-01-22, 15:14): String matching in enhanced suffix arrays
  
• Video 7-5 (2026-01-22, 13:42): The Burrows-Wheeler transform
  
• Video 7-6 (2026-01-22, 11:16): The Inverse BWT
  
• Video 7-7 (2026-01-22, 7:08): Random access in BWT-compressed texts
  
• Video 7-8 (2026-01-22, 9:08): 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:

• Bender & Farach-Colton: The Level Ancestor Problem simplified (2004), Theoretical Computer Science, 321(1), 5–12.

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

---

Unit 6  ⋅  Syllabus  ⋅  Unit 8