Step 2

We only insert those gaps of t_k into the MSA that are not already present in a_k. Also, when a gap in t_k overlaps with a gap in a_k, we only insert the the part of the gap that is not already present in a_k (see Figure 9, large X). Since each gap of t_k that is considered is inserted into all sequences $\langle a_1, .., a_{k}\rangle$, the partial score $P(\mbox{\rm A})$ is still optimal: gap against gap scores zero. In Figure 9, the up arrow correspond to this step. In the example one gap is inserted into the MSA (tall dark rectangle). The large "X" marks the gap that is already present and is therefore not inserted.

  

Figure 9: Steps 2 and 3: all gaps from t_k are inserted into the MSA, and all gaps from a_k are inserted into t_k and t_k+1