Similarly, we say p is a distance scoring function over Σ g if, for all x, y, z ∈ Σ, we have 1. p(x, x) = 0, 2. p(x, y) > 0, 3. p(x, y) = p(y, x), 4. p(x, " -") > 0, 5. p(x, z) ≤ p(x, y) + p(y, z) Definition 2.3 (Optimal Global Alignment). Let Σ be an alphabet, Σ g = Σ ∪ {" -"} be the extension of Σ with the gap character " -" and consider two strings s ∈ Σ n , t ∈ Σ m . Let α(s,t) = (s ′ ,t ′ ) be a valid global alignment of s and t (valid in the sense that it satisfies the conditions of definition 2.1), p : Σ g × Σ g → R be a scoring function over Σ g and A(s,t) be the space of all valid alignments of s and t. The score S p (α(s,t)) of α(s,t) with respect to the scoring function p is defined as