Unit 6: Suffix Trees

This unit covers suffix trees and their applications in bioinformatics.

• suffix trees
• longest common substring problem
• longest common extension problem
• suffix arrays
• LCP arrays

Material

• slides

• lecture notes

• Video 6-1 (2025-12-11, 18:38): Suffix trees
  
• Video 6-2 (2025-12-11, 13:01): Suffix tree applications
  
• Video 6-3 (2025-12-18, 25:32): Generalized suffix trees
  
• Video 6-4 (2025-12-18, 25:01): Tandem repeats
  
• Video 6-5 (2025-12-18, 7:24): Longest common extensions and suffix trees
  
• Video 6-6 (2025-12-18, 25:27): Suffix arrays and string sorting
  
• Video 6-7 (2026-01-15, 14:52): DC3 suffix array construction: induced sorting and merging
  
• Video 6-8 (2026-01-15, 16:10): DC 3 suffix array construction: final algorithm
  
• Video 6-9 (2026-01-15, 18:48): The LCP array
  
• Video 6-10 (2026-01-15, 11:10): LCP array construction
  

Further sources

Tries are notoriously treated only in passing in most algorithms and data structures textbooks, and there are various little differences in the details. Apart from the fact that they do not insist on prefix-free keys, I find the most helpful treatment of tries is given by Sedgewick and Wayne:

• Sedgewick, Wayne: Algorithms 4th edition (2011), Pearson
• Algorithms 4th ed booksite

Suffix trees:

• Gusfield: Algorithms on Strings, Trees, and Sequences (1997) Cambridge University Press
• Crochemore, Rytter: Jewels of Stringology (2002), World Scientific

Suffix arrays have not yet found widespread inclusion in standard textbooks; my way of presenting it is mostly my own, but took inspiration from

• Knut Reinert’s course on Sequence Analysis

Suffix arrays and LCP arrays are also discussed (in slightly different form) in

• Ohlebusch: Bioinformatics algorithms (2013) Oldenbusch Verlag

---

Unit 5  ⋅  Syllabus  ⋅  Unit 7