Improvement in Speed and Accuracy of Multiple Sequence Alignment Program PRIME

概要

論文の詳細を見る
Multiple sequence alignment (MSA) is a useful tool in bioinformatics. Although many MSA algorithms have been developed there is still room for improvement in accuracy and speed. We have developed an MSA program PRIME whose crucial feature is the use of a group-to-group sequence alignment algorithm with a piecewise linear gap cost. We have shown that PRIME is one of the most accurate MSA programs currently available. However PRIME is slower than other leading MSA programs. To improve computational performance we newly incorporate anchoring and grouping heuristics into PRIME. An anchoring method is to locate well-conserved regions in a given MSA as anchor points to reduce the region of DP matrix to be examined while a grouping method detects conserved subfamily alignments specified by phylogenetic tree in a given MSA to reduce the number of iterative refinement steps. The results of BAliBASE 3.0 and PREFAB 4 benchmark tests indicated that these heuristics contributed to reduction in the computational time of PRIME by more than 60% while the average alignment accuracy measures decreased by at most 2%. Additionally we evaluated the effectiveness of iterative refinement algorithm based on maximal expected accuracy (MEA). Our experiments revealed that when many sequences are aligned the MEA-based algorithm significantly improves alignment accuracy compared with the standard version of PRIME at the expense of a considerable increase in computation time.
2008-11-28

Improvement in Speed and Accuracy of Multiple Sequence Alignment Program PRIME

スポンサーリンク

概要

著者

関連論文

スポンサーリンク