World's most popular travel blog for travel bloggers.

# center star alignment induces optimal alignments on pairs with the center string?

, ,
Problem Detail:

I'm trying to follow the center star algorithm error analysis - section 6.5.3. They claim that for the center string $S_1$ the distance induced by the algorithm $d(1, j)$ is always equal the optimal alignment $D(S_1, S_j)$ since $\delta(-,-) = 0$.

I don't understand this argument. For each j, the algorithm aligns a totally different string $S'_1$ with many surplus gaps from the previous iterations.

How come we arrive to the same exact cost? Can't it be that for the new string $S'_1$ there's a very cheap alignment that would have costed lots of extra gaps if it was $S_1$?

$S'_1$ indeed can have many extra gaps over $S_1$, but it doesn't matter and the distance $d(1,j)$ between the final strings in the MA: $S'_1$ and $S'_j$ would be exactly the same as $D(S_1, S_j)$.

Why? when we start the $j$ iteration, we do an optimal global alignment between $S'_1$ and $S_j$. At first, it looks as if $S'_1$ might contain disturbing gaps, which will cause the distance to get larger than the distance to $S_1$, and helpful gaps which will cause the distance to get smaller than the distance to $S_1$. Let's show that both aren't really helpful or disturbing! suppose S1 = abc:

Disturbing gap - e.g. S'1 = ab_c and Sj = abc. as $\delta(-,-)=0$, whenever we encounter a disturbing gap at $S'_1$ we can just add an extra space to $S_j$ at no cost and get the same distance.

Helpful gap - e.g. S'1 = ab_c and Sj = abxc. It isn't really helpful, as if the global alignment would have wanted to add a gap to $S_1$, it would just add it - it makes no difference that that gap was there before we started the alignment...

Gaps added after the $j$ iteration - if the center star algorithm will add gaps to $S'_1$ in iteration $k > j$, it will always adjust strings from previous iterations with gaps at the same place, including $S_j$ - and again because $\delta(-,-)=0$ it doesn't make any difference.

To summarize - as there's no help or disturbance, the alignment distance would be exactly as the global alignment $D(S_1, S_j)$ would have wanted it, plus some extra aligned gaps which can not disturb our distance.