マルチプルアライメント

マルチプルシーケンスアライメント (multiple sequence alignment: MSA) は、複数の配列を整列させることで配列中のモチーフや保存領域を同定する手法である。進化的情報の抽出、未知のタンパク質二次構造や立体構造の予測、機能予測に広く活用されている。単にマルチプルアライメントと呼ばれることもある。ペアワイズアライメントと同様に、複数本の配列に対してもダイナミックプログラミングを解くことで厳密解を得ることは理論上は可能であるが、計算時間上またメモリ上の制約のため、様々な戦略に基づいたヒューリスティックなアルゴリズムが開発されてきた。ただし、どの手法においても最も根底を成すアイデアは、進化的な対応関係に従って配列を並べるという点にある。代表的なものには累進法および反復改善法がある。これらのアルゴリズムを採用した数多くのソフトウェアが開発されている。また、それらのソフトウェアの多くはタンパク質だけではなく核酸の配列についても適用可能である。

累進法

累進法は、プログレッシブ法 (progressive method) とも呼ばれ、ペアワイズアライメントから開始して、徐々にアラインメントを組み上げることで最終的にマルチプルアライメントを構築する方法である。アライメントを行う順番は、何らかの基準によって計算された配列ペア間の距離に基づいて構築された案内木、すなわちガイドツリー (guide tree) に従って決定される。累進法は、考えられる範疇で最もナイーブな部類のアルゴリズムであり、非常に高速にマルチプルアライメントを構築することができる。空間的な制約も大きくない。しかし、計算速度が優れている反面で、計算の初期段階においてアライメントエラーが生じた場合には、そのエラーは計算終了段階まで取り除かれないままであり、その結果、最終的に得られるアライメントの精度は反復改善法に比べて低下することが多いとされる。累進法を採用している代表的な手法としては、MAFFT、Clustal Omega、T-Coffee、ProbCons、MUSCLE、Kalign等が挙げられる。

反復改善法

反復改善法 (iterative refinement method) とは、累進法等で得られたアライメントをランダムに分割し、それらのアライメントグループを再びアライメントすることで1つのマルチプルアライメントを構築するという操作を反復することでアライメントの質を高めることを狙った方法である。この反復は評価関数の値が収束するまで繰り返される。累進法とは異なり、アライメント中に存在するエラーを取り除ける可能性があるが計算コストは累進法よりも嵩む。しかし、累進法に比べて計算量は多いものの、概ね良好なアラインメント精度を得ることができることが知られている。反復改善法を採用している方法には、MAFFT、ProbCons、MUSCLE、ClustalW等がある。

以上が代表的なアルゴリズムであるが、これらに併せて、その他には、遺伝的アルゴリズムや焼きなまし法等を利用した方法、配列間の整合性に基づいた手法 (consistency-based method) 等が開発されている。

このエントリーをはてなブックマークに追加

Site search

ページのトップへ戻る