This repo implements the Landau-Vishkin algorithm to compute the edit
distance between two strings. This is a fast method for highly similar strings.
The actual implementation follows a simplified WFA formulation
rather than the original formulation. It also learns a performance trick from
WFA. For a pair of ~5Mb HLA sequences with ~123k edits, the implementation here
can find the result in 71 seconds, faster than edlib. Edlib will be
faster for more divergent sequences.

GitHub

View Github