Improving the divide-and-conquer approach to sum-of-pairs multiple sequence alignment

We consider the problem of multiple sequence alignment: given IC sequences of length at most n and a certain scoring function, find an alignment that minimizes the corresponding ‘sum of pairs’ distance score. We generalize the ‘divide-and-conquer technique’, and present new ideas on how to use efficient search strategies for saving computer memory and acclerating the procedure for three or more sequences. Resulting running times and memory usage are shown for several test cases.