[Feature] The Smith-Waterman Algorithm

[NicklasXYZ]

The Smith-Waterman algorithm is essentially a paiwise sequence alignment algorithm typically used in bioinformatics to optimally align two (e.g. DNA) sequences.

The Smith-Waterman algorithm can be seen as a generalization of the edit distance and on the other hand the edit distance can be considered as a special case of the Smith-Waterman algorithm with specific scoring rules (giving specific weights to matching, mismatching string characters and gaps). There's more info here:

• wiki: https://en.m.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm
• an excellent python lib: https://biopython.org/docs/1.75/api/Bio.pairwise2.html

[giacomocavalieri]

Thank you for the suggestion! I'll look into it 💜

[NicklasXYZ]

@giacomocavalieri Beyond this algorithm (which might not strictly be measuring an edit distance), would you also take PR's for:

• Hamming Distance: An edit distance with the substitution operation allowed.
• Longest common subsequence: An edit distance with the insertion and deletion operations allowed.
• Unrestricted Damerau–Levenshtein: An edit distance with the insertion, deletion, substitution and unrestricted transpotition operations allowed.

[giacomocavalieri]

Sure!