Alignment of three sequences in quadratic space
Xiaoqiu Huang · ACM SIGAPP Applied Computing Review · 1993
We present a dynamic programming algorithm for computing an optimal global alignment of three sequences in quadratic space. The algorithm has been implemented as a portable C program. The program makes it possible to align simultaneously any three protein sequences on workstations with tens of megabytes of main memory. This rigorous program is used as a benchmark to evaluate the performance of a heuristic multiple sequence alignment program on protein sequences from the Protein Identification Resource protein sequence database. Experimental results indicate that the rigorous program may perform significantly better than the heuristic program on three sequences of weak similarity. We also describe algorithms for computing local alignments among three sequences in quadratic space.