). Let Σ be an alphabet, Σ g = Σ ∪ {" -"} be the extension of Σ with the gap character " -" and p : Σ g × Σ g → R be a function defined over the elements of Σ g . We say p is a similarity scoring function over Σ g if, for all x, y ∈ Σ, we have