10 - Multiple Sequence Alignment II

Summary

In the previous chapter we saw that finding the very best multiple alignment of a large number of sequences is difficult for two different reasons. First, although the direct method is general, it seems to require a different program text for each different number of sequences. Second, if there are K sequences of roughly equal length then the number of entries in the dynamic programming table increases as fast as the K th power of the length, and the time required to fill each entry increases as the K th power of 2.

In this chapter, we will address both of these difficulties to some degree. It is, in fact, possible to create a single program text that works for any number of strings. And, although some inputs seem to require that nearly all of the table entries be filled in, careful analysis of the inputs supplied on a particular run will often help us to avoid filling large sections of the table that have no influence on the final alignment. Part of this analysis can be performed by the heuristic methods described in the previous chapter, since better approximate alignments help our method search more quickly for the best alignment.

Pushing through the Matrix by Layers

As a comfortable context for learning two of the techniques used in our program, we will begin by modifying Chapter 3's subroutine similarity for computing the similarity of two sequences.