Edit Sequence, constant-size alphabet (Sequence Alignment)

From Algorithm Wiki
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