main page — CS 594 Algorithms of Bioinformatics
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
- Video 5-1 (2025-12-04):
The read mapping problem in bioinformatics
- Video 5-2 (2025-12-04):
String matching with automata
- Video 5-3 (2025-12-04):
The Knuth-Morris-Pratt algorithm
- Video 5-4 (2025-12-04):
The Aho-Corasick algorithm
- Video 5-5 (2025-12-11):
Inexact matching via alignments
- Video 5-6 (2025-12-11):
k-Mismatch Matching, Longest common extensions
- Video 5-7 (2025-12-11):
SNPs, alignment seeds
Further sources
String matching with automata and the Knuth-Morris-Pratt are discussed, e.g., in
The Aho-Corasick algorithm is discussed in detail, e.g., in