DocumentCode :
3230238
Title :
ClustalY: speed up the guide tree building for ClustalW
Author :
Yu, Huan ; Deng, Minghua
Author_Institution :
Sch. of Math. Sci., Peking Univ.
fYear :
2005
fDate :
1-1 July 2005
Lastpage :
610
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
High-Performance Computing in Asia-Pacific Region, 2005. Proceedings. Eighth International Conference on
Conference_Location :
Beijing
Print_ISBN :
0-7695-2486-9
Type :
conf
DOI :
10.1109/HPCASIA.2005.26
Filename :
1592329
Link To Document :
بازگشت