Tree or hierarchical methods using dynamic programming

Practical methods for multiple sequence alignment based on a tree have been developed in several laboratories [49][48][47][46][38]. The principle is that since the alignment of two sequences can be achieved very easily, multiple alignments should be built by the successive application of pairwise methods.

The steps are summarised here and illustrated in Figure 5:

• Compare all sequences pairwise. For sequences there are pairs.

• Perform cluster analysis on the pairwise data to generate a hierarchy for alignment. This may be in the form of a binary tree, or a simple ordering.

• Build the multiple alignment by first aligning the most similar pair of sequences, then the next most similar pair and so on. Once an alignment of two sequences has been made, then this is fixed. Thus for a set of sequences A, B, C, D having aligned A with C and B with D the alignment of A, B, C, D is obtained by comparing the alignments of A and C with that of B and D using averaged scores at each aligned position.

This family of methods gives good usable alignments with gaps it can be applied to large numbers of sequences, and with the exception of the initial pairwise comparison step is very fast.

Although based on the successive application of pairwise methods, multiple alignment will often yield better alignments than any pair of sequences taken in isolation. This effect was illustrated by Barton and Sternberg [46] for the alignment of immunoglobulin and globin domains. Figure 6 shows that for some alignment pairs there is a marked improvement in accuracy over optimal pairwise aligment (e.g. variable versus constant domains).