Improvement in speed and accuracy of multiple sequence alignment program prime

Shinsuke Yamada*, Osamu Gotoh, Hayato Yamana


研究成果: Article査読

3 被引用数 (Scopus)


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.

ジャーナルIPSJ Transactions on Bioinformatics
出版ステータスPublished - 2008 11月

ASJC Scopus subject areas

  • 生化学、遺伝学、分子生物学(その他)
  • コンピュータ サイエンスの応用


「Improvement in speed and accuracy of multiple sequence alignment program prime」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。