Edit Sequence, constant-size alphabet

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.

Parameters

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 2 of 2 algorithms

				See more
Gapped BLAST	1997	$O(mn)$	$O(mn)$
Basic Local Alignment Search Tool (BLAST)	1990	$O(mn)$	$O(mn)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms