next up previous
Next: Step 3 Up: Near Optimal Multiple Sequence Previous: SP alignment and Maximum

Step 2

We only insert those gaps of tk into the MSA that are not already present in ak. Also, when a gap in tk overlaps with a gap in ak, we only insert the the part of the gap that is not already present in ak (see Figure 9, large X). Since each gap of tk 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 tk are inserted into the MSA, and all gaps from ak are inserted into tk and tk+1
\mbox{\psfig{file=align3.EPS,height=0.18\textheight,angle=0} }

Chantal Korostensky