  Multiple sequence alignment is increasingly important to bioinformatics, with
several applications ranging from phylogenetic analyses to domain
identification. There are several ways to perform multiple sequence alignment,
an important way of which is the progressive alignment approach studied in this
work. Progressive alignment involves three steps: find the distance between
each pair of sequences; construct a guide tree based on the distance matrix;
finally based on the guide tree align sequences using the concept of aligned
profiles. Our contribution is in comparing two main methods of guide tree
construction in terms of both efficiency and accuracy of the overall alignment:
UPGMA and Neighbor Join methods. Our experimental results indicate that the
Neighbor Join method is both more efficient in terms of performance and more
accurate in terms of overall cost minimization.
