0
$\begingroup$

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$?

$\endgroup$

1 Answer 1

0
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.