Unit 5: String Matching

This unit covers the read mapping problem and classic string-matching algorithms to solve it.

• the read mapping problem in bioinformatics
• string matching with automata
• the Knuth-Morris-Pratt (KMP) algorithm
• the Aho-Corasick algorithm
• inexact string matching (approximate matching)

Material

• slides

• lecture notes

• Video 5-1 (2025-12-04, 17:13): The read mapping problem in bioinformatics
  
• Video 5-2 (2025-12-04, 32:15): String matching with automata
  
• Video 5-3 (2025-12-04, 14:23): The Knuth-Morris-Pratt algorithm
  
• Video 5-4 (2025-12-04, 20:00): The Aho-Corasick algorithm
  
• Video 5-5 (2025-12-11, 9:00): Inexact matching via alignments
  
• Video 5-6 (2025-12-11, 16:12): k-Mismatch Matching, Longest common extensions
  
• Video 5-7 (2025-12-11, 17:35): SNPs, alignment seeds
  

Further sources

String matching with automata and the Knuth-Morris-Pratt are discussed, e.g., in

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

The Aho-Corasick algorithm is discussed in detail, e.g., in

• Schwarz: CS166 Advanced Data Structures - Aho Corasick Automata, Stanford University

---

Unit 4  ⋅  Syllabus  ⋅  Unit 6