累進法

ウィキペディア小見出し辞書

累進法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2014/10/19 20:24 UTC 版)

「多重整列」の記事における「累進法」の解説

計算量を抑えるためによく使われているヒューリスティクスが、累進法とよばれる階層的に多重整列を求める方法である。まず総当たりのペアワイズアラインメントを行って「ガイドツリー」と呼ばれる近似的な系統樹を作り、最もよく似たペアから始めて段階的に配列を付け加えていく。ガイドツリーは近隣結合法ないし非加重結合法による階層型クラスタリングによって作られる。 累進法で求める多重整列は大域的に最適であることを保証されない。配列を付け加えていく過程で局所最適な整列が行われると、それが以降最後まで維持されてしまう。また最初に作られるペアワイズアラインメントに依存しているため、類似性が低い配列に対して実施するとうまく機能しないという問題もある。比較的新しいアルゴリズムでは多重整列の評価関数に非線形的な補正を加えることで精度を上げているものが多い。 しかし累進法は、比較的多量の配列（数百から数千）に対して現実的な時間で計算を終えることができる。頻用されているのはClustalシリーズで、様々な機関がwebサーバー上で多重整列を計算できるように提供している。T-CoffeeはClustalよりも時間がかかるが、類似性が低い配列に対しても一般的により良いアラインメントを求めることができる。