Edit Sequence, constant-size alphabet (Sequence Alignment)
Jump to navigation
Jump to search
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
References/Citation
https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub