Phylogenetic Trees and Multiple Alignments

Iterative alignment strategy

The aim is to reduce the problem of a multiple alignment to an iteration of pairwise alignments.

The procedure works as follows:

• Compute all pairwise distances between given sequences
• Compute a tree by single linkage clustering
• Align the sequences in bottom up order, see figure:

The bottom up alignment requires comparing groups of pre-aligned sequences. This is achieved by using profile alignment. Profile alignment relies on a NW like algorithm, however with scores defined as average scores among columns of pre-aligned sequence groups.

Again the concept of the edit matrix is used to obtain a dynamic programming algorithm. A possibility to treat the gaps in profile alignments is to look into the profiles and to overtake gap-penalties to the edit matrix.

Advantages of iterative alignment procedure:

• profile alignment reflects the conservation within a group (biologically relevant)
• it's fast and scales to large numbers of sequences

Disadvantages:

• unclear objective function
• misalignments introduced during the procedure are kept