Carrillo$-$Lipman $[10$ points$]$

We consider the Weighted SP$-$Edit Distance problem, where we are given se$-$

quences $v_1,$dots,$v_{k}in{}^{*}$ each with length $n$ and a scoring function $$:$(\{-\})$

$(\{-\})R.$ The task is to find a multiple alignment A such that $SP(A)$ is min$-$

imum. We use the Carrillo$-$Lipman algorithm. Let $v_{i,j}$ denote the prefix $v_{i,1}dots{v}_{i,j}$ of

sequence $v_i$ of length $j.$ Briefly, $D(i_1,$dots,$i_k)$ denotes the minimum cost of aligning the

$k$ prefixes $v_{1,i_1},$dots,$v_{k,i_k}.$ On the other hand, $D_{a,b}^{+}(i,j)$ denotes the minimum cost of

the pairwise alignment of suffixes $v_{a,i}$ and $v_{b,j}.$ In Lecture $7,$ we considered the $k=3$

case. We learned that given a heuristic solution with cost $z,$ we know that the optimal

alignment does not pass through vertex $(i_1,i_2,i_3)$ if

$D(i_1,i_2,i_3)+D_{1,2}^{+}(i_1,i_2)+D_{1,3}^{+}(i_1,i_3)+D_{2,3}^{+}(i_2,i_3)>z$

a$.$ Consider the general case with kinN sequences. Let $(i_1,$dots,$i_k)in[n{]}^k$ and let

$D(i_1,$dots,$i_k)$ be the optimal cost for aligning prefixes $v_{1,i_1},$dots,$v_{k,i_k}.$ Let $z$ be the

cost of an alignment of $v_1,$dots,$v_k.$ Under which condition do we know that the

optimal alignment does not pass through vertex $(i_1,$dots,$i_k)?[5$ points$]$

Hint: Update Equation $(1).$