Title :
ClustalY: speed up the guide tree building for ClustalW
Author :
Yu, Huan ; Deng, Minghua
Author_Institution :
Sch. of Math. Sci., Peking Univ.
Abstract :
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
Keywords :
biology computing; computational complexity; genetics; optimisation; trees (mathematics); ClustalW; ClustalY; NP-hard problem; guide tree building; heuristic approach; optimal multiple sequences alignment; pairwise alignments; pairwise distance matrix; Biology; Buildings; DNA; Dynamic programming; Frequency; Genetic mutations; Length measurement; NP-hard problem; Proteins; Sequences;
Conference_Titel :
High-Performance Computing in Asia-Pacific Region, 2005. Proceedings. Eighth International Conference on
Conference_Location :
Beijing
Print_ISBN :
0-7695-2486-9
DOI :
10.1109/HPCASIA.2005.26