Next: Experimental Results Up: Methods Previous: An Algorithm For Finding

## Improving Alignments With Gap Blocks

Definition 3.5   The score S(B) of a block is the maximum possible score of the MSA that can be obtained by shifting the gaps in that correspond to the gaps within the block B.

Once we have all the gap blocks we can optimize the MSA by shifting the gaps in each B that correspond to the real gaps in the alignment . The problem is that some gap blocks may overlap, that is two different gap blocks Bi and Bj may share the same gaps. Of course, only either Bi or Bj can be chosen in the final alignment. Whenever this happens, we want to select the block with the best score. For any two blocks Bi, Bj in P, if the block Bi overlaps with some other block Bj, score both according to Definition and remove the block with the lower score from P. For each block B in P, shift and combine the gaps in the MSA that correspond to the block Bi and keep the change if the score increases.
Example 3.2:  After applying the above procedures to the MSA in Figure , we end up with an MSA that has a much better score and only has 4 indel events. In addition, we can use the gaps of the MSA to construct the corresponding evolutionary tree (see Section 4).

Score of the alignment: 2400.081
Maximum possible score: 2472.632