Trees, Stars, and Multiple Biological Sequence Alignment

One important problem in biological sequence comparison is how to simultaneously align several nucleic acid or protein sequences. A multiple alignment avoids possible inconsistencies among several pairwise alignments and can elucidate relationships not evident from pairwise comparisons. The basic dynamic programming algorithm for optimal multiple sequence alignment requires too much time to be practical for more than three sequences, the length of an average protein. Recently, Carrillo and Lipman (SIAMJ. Appl. Math., 48 (1988), pp. 1073–1082) have rendered feasible the optimal simultaneous alignment of as many as six sequences by showing that a consideration of minimal pairwise alignment costs can vastly decrease the number of cells a dynamic programming algorithm need consider. Their argument, however, requires the cost of a multiple alignment to be a weighted sum of the costs of its projected pairwise alignments.This paper presents an extension of Carrillo and Lipman's algorithm to the definition of multiple alignment cost as the cost of an evolutionary tree. An interesting generalization of the linear programming problem arises from the analysis.