A New Progressive Multiple Sequence Alignment Algorithm

In this paper, we present a new progressive algorithm for Multiple Sequence Alignment (MSA). Our algorithm adopts a new distance, called anchor distance to compute the distance between two protein sequences, and a variant of the UPGMA method to construct a guide tree. Our algorithm implements also a refinement step. Our algorithm is of complexity O(N⁴+N*L²) in computing time, where N is the number of the sequences and L is the length of the longest sequence. We asses our algorithm on different protein benchmarks, e.g., BALIBASE, HOMSTRAD, OXBENCH, and we compared the obtained results to those obtained with other alignment algorithms, e.g., CLUSTALW, MUSCLE, MAFFT and PROBCONS, using the Column Score (CS) and the Sum of Pairs Score (SPS). We obtained good results.