Extension of dynamic programming to more than two sequences

Needleman and Wunsch [13] suggested that their dynamic programming algorithm could be extended to the comparison of many sequences. Waterman et al. [27] also described how dynamic programming could be used to align more than two sequences. In practice, the need to store an dimensional array (where is the number of sequences) limits these extensions to three-sequence applications. In addition, the time required to perform the comparison of three sequences is proportional to . Murata et al. [44] described a modification of the Needleman and Wunsch procedure for three sequences which ran in time proportional to ; unfortunately this approach required an additional three dimensional array thus further limiting its application to short sequences. One of the earliest practical applications of dynamic programming to multiple alignment was the work of Sankoff et al. [45] who aligned nine 5S RNA sequences that were linked by an evolutionary tree. Their algorithm which also constructed the protosequences at the interior nodes of the tree was made computationally feasible by decomposing the nine-sequence problem into seven three sequence alignments. The alignments were repeatedly performed working in from the periphery of the tree until no further change occurred to the protosequences.