|
早稲田大学
山名 早人
教授
機関別共同研究
Discovery Saga
論文分野別Discovery Saga
研究テーマDiscovery Saga
協賛企業
共同研究先:Kyoto University
Academic
共同研究数 2
Article
2008 11
情報処理学会 : Information Processing Society of Japan
Improvement in speed and accuracy of multiple sequence alignment program prime
(Last author)
多重配列アライメントプログラムprimeの高速化・高精度化
Shinsuke Yamada, Osamu Gotoh, Hayato Yamana
IPSJ Transactions on Bioinformatics
【抄録】
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 Information Processing Society of Japan.
【抄録日本語訳】
複数配列アライメント(MSA)は、バイオインフォマティクスにおける有用なツールである。これまで多くのMSAアルゴリズムが開発されてきましたが、精度や速度に改善の余地が残されています。我々は、MSAプログラムPRIMEを開発した。その重要な特徴は、区分的線形ギャップコストを持つグループ間配列アライメントアルゴリズムを使用することである。その結果、PRIMEは現在利用可能なMSAプログラムの中で最も精度の高いプログラムの一つであることを示しました。しかし、PRIMEは他の主要なMSAプログラムより遅い。計算性能を向上させるために、我々はPRIMEにアンカリングとグループ化ヒューリスティックを新たに組み込んだ。アンカリング法は、与えられたMSAの中から保存状態の良い領域をアンカーポイントとして見つけ出し、調べるべきDPマトリックスの領域を減らすものである。一方、グルーピング法は、与えられたMSAの中から系統樹によって指定された保存されたサブファミリーアラインメントを見つけ出し、反復精密化ステップの回数を減らすための方法である。BAliBASE 3.0とPREFAB 4のベンチマークテストの結果、これらのヒューリスティクスはPRIMEの計算時間を60%以上短縮する一方で、平均アライメント精度は最大2%低下することが示された。さらに、最大期待精度(MEA)に基づく反復精緻化アルゴリズムの有効性を評価した。その結果、多数の配列がアラインメントされる場合、MEAに基づくアルゴリズムは、計算時間の大幅な増加を犠牲にして、PRIMEの標準バージョンと比較してアラインメント精度を大幅に向上させることが明らかになった。© 2008 情報処理学会.
Article
2006
Springer
Improvement in accuracy of multiple sequence alignment using novel group-to-group sequence alignment algorithm with piecewise linear gap cost
(Last author)
部分線形ギャップコストを用いた新規グループ間配列アライメントアルゴリズムによる多重配列アライメント精度の向上
Shinsuke Yamada, Osamu Gotoh, Hayato Yamana
BMC Bioinformatics
【抄録】
Background: 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. In the alignment of a family of protein sequences, global MSA algorithms perform better than local ones in many cases, while local ones perform better than global ones when some sequences have long insertions or deletions (indels) relative to others. Many recent leading MSA algorithms have incorporated pairwise alignment information obtained from a mixture of sources into their scoring system to improve accuracy of alignment containing long indels. Results: We propose a novel group-to-group sequence alignment algorithm that uses a piecewise linear gap cost. We developed a program called PRIME, which employs our proposed algorithm to optimize the well-defined sum-of-pairs score. PRIME stands for Profile-based Randomized Iteration MEthod. We evaluated PRIME and some recent MSA programs using BAliBASE version 3.0 and PREFAB version 4.0 benchmarks. The results of benchmark tests showed that PRIME can construct accurate alignments comparable to the most accurate programs currently available, including L-INS-i of MAFFT, ProbCons, and T-Coffee. Conclusion: PRIME enables users to construct accurate alignments without having to employ pairwise alignment information. PRIME is available at http://prime.cbrc.jp/. © 2006 Yamada et al; licensee BioMed Central Ltd.
【抄録日本語訳】
背景 複数配列アライメント(MSA)は、バイオインフォマティクスにおける有用なツールである。これまで多くのMSAアルゴリズムが開発されてきたが、精度や速度に改善の余地が残されている。タンパク質配列のアラインメントでは、多くの場合、グローバルMSAアルゴリズムの方がローカルMSAアルゴリズムよりも性能が良いが、一部の配列が他と比べて長い挿入や欠失(indel)を持つ場合には、ローカルMSAアルゴリズムの方がグローバルMSAアルゴリズムよりも性能が良い。最近の多くのMSAアルゴリズムは、長いインデルを含むアライメントの精度を向上させるために、様々なソースから得られたペアワイズアライメント情報をスコアリングシステムに組み込んでいます。結果 我々は、区分的線形ギャップコストを用いた新しいグループ間配列アライメントアルゴリズムを提案する。また、提案したアルゴリズムを用いて、定義されたペアスコア和を最適化するプログラム「PRIME」を開発した。PRIMEはProfile-based Randomized Iteration MEthodの略である。BAliBASE version 3.0とPREFAB version 4.0のベンチマークを用いて、PRIMEと最近のMSAプログラムの評価を行った。ベンチマークテストの結果、PRIMEはMAFFTのL-INS-i、ProbCons、T-Coffeeなど、現在利用可能な最も精度の高いプログラムに匹敵する精度のアライメントを構築できることが示された。結論 PRIMEは、ペアワイズアライメント情報を用いることなく、高精度なアライメントを構築することを可能にする。PRIMEはhttp://prime.cbrc.jp/で公開されています。© 2006 Yamada et al; licensee BioMed Central Ltd. All rights reserved.