Multiple sequence alignment using anchor points through generalized dynamic programming
Jérôme Gracy, Jean Sallantin · 1994
A generalization of the dynamic programming algorithm applied to the multiple alignment of protein sequences is proposed. The algorithm has two main procedures: (i) local correspondences between sequences - hereafter called anchor points - are selected according to a criterion that combines local and global simlilarity values, (ii) the alignment is constructed recursively by choosing and linking together the optimal anchor points. This multiple sequence alignment algorithm achieves a good compromise between the O(L ) complexity of the exhaustive dynamic programming approach applied to N sequences of length L and the poor quality of the alignments obtained with methods based on a hierarchical clustering of the sequences.