PAAA: A Progressive Iterative Alignment Algorithm Based on Anchors

摘要

In this paper, we present a new iterative progressive algorithm for Multiple Sequence Alignment (MSA), called Progressive Iterative Alignment Algorithm Based on Anchors (PAAA). Our algorithm adopts a new distance, called anchor distance to compute the distance between two sequences, and a variant of the UPGMA method to construct a guide tree. PAAA is of complexity O(N~4 + N*L~2) in computing time, where N is the number of the sequences and L is the length of the longest sequence. We benchmarked PAAA using different benchmarks, e.g., BALIBASE, HOMSTRAD, OXBENCH and BRALIBASE, and we compared the obtained results to those obtained with other alignment algorithms, e.g., CLUSTALW, MUSCLE, MAFFT and PROBCONS, using us criteria the Column Score (CS) and the Sum of Pairs Score (SPS). We obtained good results for protein sequences.