Edit Sequence, constant-size alphabet (Sequence Alignment)

From Algorithm Wiki
Revision as of 09:07, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


Given two strings, determine the shortest sequence of edits required to transform one of the strings into the other. Assume we have a constant-size alphabet.

Related Problems

Generalizations: Edit Distance, constant-size alphabet


$m,n$: lengths of input strings; assume $m\leq n$

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Gapped BLAST 1997 $O(mn)$ $O(mn)$? Exact Deterministic Time
Basic Local Alignment Search Tool (BLAST) 1990 $O(mn)$ $O(mn)$? Exact Deterministic Time

Time Complexity Graph

Sequence Alignment - Edit Sequence, constant-size alphabet - Time.png