Edit Sequence, constant-size alphabet (Sequence Alignment)

Description

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

Parameters

$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

Space Complexity Graph

Time-Space Tradeoff

References/Citation

https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub