case 2. π(t) has k ≥ 2 repeats. In this case, the middle alignment is not empty since it contains tk. The last column in the middle alignment has three configurations: (a) the last column contains two letters s[j - i] and s[j], (b) the last column contains a space and the letter s[j], (c) the last column contains the letter s[j - i] and a space. For sub-case (a), if we take away the last letter s[j] from the self alignment of π(t), we can get a self alignment of π'(t'), where t' ∈ Tj-1, π'(t') ∈ Π(t', i) and V(π'(t'), c, i) = w(i, j - 1). By comparing the two self alignment, we have V(π(t , c, i = V(π'(t'), c, i) + μ(s[j - i], s[j]) = w(i, j - 1) + μ(s[j - i], s[j]). For sub-case (b), if we take away the last letter s[j] and space aligned with s[j] from the self alignment of π(t), we can get a self alignment of π'(t'), where t' ∈ Tj-1, π'(t') ∈ Π(t', i - 1) and V(π'(t'), c, i) = w(i - 1, j - 1). Notice that in the end of the self alignment of π'(t'), there are only i - 1 letters mapped to spaces with score , and there is one more letter in the self alignment of π(t) mapped to spaces with score . Thus, V(π(t), c, i) = w(i - 1, j - 1) + μ(Δ, s[j]) + . For sub-case (c), π(t) ∈ Π(t, i + 1). We can impose that the alignment of the letter s[j - i] and the space is scored as , not μ(s[j - i], Δ). From V(π(t), c, i + 1) = w(i + 1, j), we have V(π(t), c, i) = w(i + 1, j) + μ(s[j - i], Δ) - . □