Edit distance and sequence alignment
12 methods in the atlas attack this one problem. They are rivals: each wins something the others do not.
Phrasings that mean this problem
Edit distanceBounded edit distanceSpeedup for edit distanceSequence similaritySequence symmetryTransposition-aware distanceGlobal sequence alignmentLocal sequence alignmentSequence alignmentSimilar-sequence alignmentLinear-space alignmentSequence comparison
dynamic-programming
- Longest common subsequencestandalonecanondynamic-programming
- Longest palindromic subsequencestandalonestandarddynamic-programming
strings
- Suffix tree matching statisticsstandalonespecialiststrings
- Hirschberg's algorithmDivide-and-conquer LCSstandardstrings
- Needleman-Wunschstandalonecanonstrings
- Smith-WatermanZero-floored local scorescanonfull lesson ▸strings
- Gotoh's algorithmAffine gap penaltiesstandardstrings
- Banded alignmentDiagonal band restrictionstandardstrings
- Four-Russians alignmentBlock lookup tablesspecialiststrings
- Wagner-FischerPrefix-to-prefix tablecanonfull lesson ▸strings
- Ukkonen's edit distanceDiagonal cutoff for bounded kspecialiststrings
- Damerau-Levenshteinstandalonestandardstrings