ClustalY: Speed up the guide tree building for ClustalW

Since finding an optimal multiple sequences alignment is a NP-hard problem, various heuristic approaches have been proposed. The popular sequence alignment program ClustalW uses the progressive alignment. This approach works by aligning sequences using a series of pairwise alignments with a guide tree. A pairwise distance matrix is calculated to construct the guide tree to show the evolutionary relationship of the sequences. We use a faster algorithm to replace the two algorithms come with the current ClustalW to calculate the distance matrix. Experimental results show that speedup of over 10 is obtainable for the guide tree building stage with acceptable little loss of accuracy. Supplementary: http://ctb.pku.edu.cn/~yuhuan ? 2005 IEEE.EI