). Let Σ be an alphabet and let s ∈ Σ n and t ∈ Σ m be two strings over Σ. Define Σ g = Σ ∪ {" -"} as the extension of Σ with the gap character " -". The tuple α(s,t) = (s ′ ,t ′ ) is a global alignment of sequences s and t if and only if