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

###### Asked By : ihadanny

###### Answered By : ihadanny

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

Question Source : http://cs.stackexchange.com/questions/66555

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback