Repository: fulcrumgenomics/fgpyo (language: python)

Issue:
Feature request: support sequence distance functions
Could be helpful to have Hamming and Levenshtein distance available


Discussion / hints:
Quick question, do we want the functions to worry about case? Or do we want the user to worry about case?

```python
hamming("AAA", "aaa") == 0 # function worries about case
hamming("AAA", "aaa") == 3 # user worries about case
```

Fix patch:
diff --git a/fgpyo/sequence.py b/fgpyo/sequence.py
index ff5bc7bb..d8ab32ec 100644
--- a/fgpyo/sequence.py
+++ b/fgpyo/sequence.py
@@ -2,9 +2,15 @@
 # Utility Functions for Manipulating DNA and RNA sequences.
 
 This module contains utility functions for manipulating DNA and RNA sequences.
+
+
+`levenshtein` and `hamming` functions are included for convenience.
+If you are performing many distance calculations, using a C based method is preferable.
+ex. https://pypi.org/project/Distance/
 """
 
 from typing import Dict
+from typing import List
 
 _COMPLEMENTS: Dict[str, str] = {
     # Discrete bases
@@ -94,3 +100,67 @@ def gc_content(bases: str) -> float:
         return 0
     gc_count = sum(1 for base in bases if base == "C" or base == "G" or base == "c" or base == "g")
     return gc_count / len(bases)
+
+
+def hamming(string1: str, string2: str) -> int:
+    """
+    Calculates hamming distance between two strings, case sensitive.
+    Strings must be of equal lengths.
+
+    Args:
+        string1: first string for comparison
+        string2: second string for comparison
+
+    Raises:
+        ValueError: If strings are of different lengths.
+    """
+    if len(string1) != len(string2):
+        raise ValueError(
+            "Hamming distance requires two strings of equal lengths."
+            f"Received {string1} and {string2}."
+        )
+    return sum([string1[i] != string2[i] for i in range(len(string1))])
+
+
+def levenshtein(string1: str, string2: str) -> int:
+    """
+    Calculates levenshtein distance between two strings, case sensitive.
+
+    Args:
+        string1: first string for comparison
+        string2: second string for comparison
+
+    """
+    N: int = len(string1)
+    M: int = len(string2)
+    if N == 0 or M == 0:
+        return max(N, M)
+    # Initialize N + 1 x M + 1 matrix with final row/column representing the empty string.
+    # Fill in initial values for empty string sub-problem comparisons.
+    #   A D C "
+    # A - - - 3
+    # B - - - 2
+    # C - - - 1
+    # " 3 2 1 0
+    matrix: List[List[int]] = [[int()] * (M + 1) for _ in range(N + 1)]
+    for j in range(M + 1):
+        matrix[N][j] = M - j
+    for i in range(N + 1):
+        matrix[i][M] = N - i
+    # Fill in matrix from bottom up using previous sub-problem solutions.
+    #   A D C "      A D C "      A D C "      A D C "      A D C "
+    # A - - - 3    A - - - 3    A - - 2 3    A - 2 2 3    A 1 2 2 3
+    # B - - - 2 -> B - - 1 2 -> B - 1 1 2 -> B 2 1 1 2 -> B 2 1 1 2
+    # C - - 0 1    C - 1 0 1    C 2 1 0 1    C 2 1 0 1    C 2 1 0 1
+    # " 3 2 1 0    " 3 2 1 0    " 3 2 1 0    " 3 2 1 0    " 3 2 1 0
+    for i in range(N - 1, -1, -1):
+        for j in range(M - 1, -1, -1):
+            if string1[i] == string2[j]:
+                matrix[i][j] = matrix[i + 1][j + 1]  # No Operation
+            else:
+                matrix[i][j] = 1 + min(
+                    matrix[i + 1][j],  # Deletion
+                    matrix[i][j + 1],  # Insertion
+                    matrix[i + 1][j + 1],  # Substitution
+                )
+    return matrix[0][0]


Test patch:
diff --git a/tests/fgpyo/test_sequence.py b/tests/fgpyo/test_sequence.py
index f9d16414..d810ea09 100644
--- a/tests/fgpyo/test_sequence.py
+++ b/tests/fgpyo/test_sequence.py
@@ -3,6 +3,8 @@
 import pytest
 
 from fgpyo.sequence import gc_content
+from fgpyo.sequence import hamming
+from fgpyo.sequence import levenshtein
 from fgpyo.sequence import longest_hp_length
 from fgpyo.sequence import reverse_complement
 
@@ -54,3 +56,58 @@ def test_homopolymer(bases: str, expected_hp_len: int) -> None:
 )
 def test_gc_content(bases: str, expected_gc_content: float) -> None:
     assert gc_content(bases) == expected_gc_content
+
+
+@pytest.mark.parametrize(
+    "string1, string2, hamming_distance",
+    [
+        ("", "", 0),
+        ("AAA", "AAA", 0),
+        ("ABC", "ABC", 0),
+        ("AAC", "ABC", 1),
+        ("AAC", "BBC", 2),
+        ("CBA", "ABC", 2),
+        ("AAA", "BBB", 3),
+        ("AbC", "ABC", 1),
+        ("abc", "ABC", 3),
+        ("hamming", "hamning", 1),
+    ],
+)
+def test_hamming(string1: str, string2: str, hamming_distance: int) -> None:
+    assert hamming(string1, string2) == hamming_distance
+
+
+@pytest.mark.parametrize(
+    "string1, string2",
+    [
+        ("", "A"),
+        ("AB", "ABC"),
+        ("A", ""),
+    ],
+)
+def test_hamming_with_invalid_strings(string1: str, string2: str) -> None:
+    with pytest.raises(ValueError):
+        hamming(string1, string2)
+
+
+@pytest.mark.parametrize(
+    "string1, string2, levenshtein_distance",
+    [
+        ("", "", 0),
+        ("AAA", "AAA", 0),
+        ("ABC", "ABC", 0),
+        ("AAC", "ABC", 1),
+        ("AAC", "BBC", 2),
+        ("CBA", "ABC", 2),
+        ("AAA", "BBB", 3),
+        ("AbC", "ABC", 1),
+        ("abc", "ABC", 3),
+        ("AB", "ABC", 1),
+        ("ABC", "AB", 1),
+        ("CC", "AAA", 3),
+        ("CAC", "AAA", 2),
+        ("lenvestein", "levenshtein", 3),
+    ],
+)
+def test_levenshtein_dynamic(string1: str, string2: str, levenshtein_distance: int) -> None:
+    assert levenshtein(string1, string2) == levenshtein_distance