多重整列
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2014/10/19 20:24 UTC 版)
ナビゲーションに移動 検索に移動
アルゴリズム
多重整列を手作業で行うことも不可能ではないが、通常はコンピューターに計算させる。配列を1対1で整列させるペアワイズアラインメント(pairwise alignment)よりも計算複雑性が高く、より洗練されたアルゴリズムが必要となる。最適な多重整列を求めるには非現実的な計算量が要求されるため、一般に用いられているプログラムはヒューリスティクスを用いている。
動的計画法
大局的に最適な多重整列を求めるためには動的計画法を用いる。アミノ酸配列の場合は、ギャップペナルティと、あるアミノ酸から他のアミノ酸への置換の起こりやすさを示す置換行列をパラメータとして与える。核酸配列の場合にもギャップペナルティと置換行列を用いるが、置換行列は置換が起きるか否かのみを考慮した単純なものを使う場合が多い。
独立したn個の配列を整列するために、単純にはペアワイズアラインメントをn次元に拡張すれば良い。しかしnの増加に伴って計算量が指数的に増加し（配列の長さをLとしてO(Ln)）、NP完全であることが示されている。[1][2][3]
累進法
計算量を抑えるためによく使われているヒューリスティクスが、累進法とよばれる階層的に多重整列を求める方法である。まず総当たりのペアワイズアラインメントを行って「ガイドツリー」と呼ばれる近似的な系統樹を作り、最もよく似たペアから始めて段階的に配列を付け加えていく。ガイドツリーは近隣結合法ないし非加重結合法による階層型クラスタリングによって作られる。[4]
累進法で求める多重整列は大域的に最適であることを保証されない。配列を付け加えていく過程で局所最適な整列が行われると、それが以降最後まで維持されてしまう。また最初に作られるペアワイズアラインメントに依存しているため、類似性が低い配列に対して実施するとうまく機能しないという問題もある。比較的新しいアルゴリズムでは多重整列の評価関数に非線形的な補正を加えることで精度を上げているものが多い。[4]
しかし累進法は、比較的多量の配列（数百から数千）に対して現実的な時間で計算を終えることができる。頻用されているのはClustalシリーズ[5][6]で、様々な機関がwebサーバー上で多重整列を計算できるように提供している。T-Coffee[7]はClustalよりも時間がかかるが、類似性が低い配列に対しても一般的により良いアラインメントを求めることができる。
反復法
累進法の欠点を克服するため、新たな配列を付け加える際にそれまで出来ている部分も整列し直すアプローチがあり、総じて「反復法」と呼ばれている。累進法では、一度多重整列に組み込まれた配列は、それ以後再検討されることなく最終結果に反映されてしまう。これは正確性を犠牲にして効率を取ったためである。対照的に反復法では、一度得た多重整列を繰り返し再構築することで精度を高めようとする。[4]
- ^ Wang L, Jiang T (1994). “On the complexity of multiple sequence alignment”. J Comput Biol 1 (4): 337–348. doi:10.1089/cmb.1994.1.337. PMID 8790475.
- ^ Just W (2001). “Computational complexity of multiple sequence alignment with SP-score”. J Comput Biol 8 (6): 615–23. doi:10.1089/106652701753307511. PMID 11747615.
- ^ Elias, Isaac (2006). “Settling the intractability of multiple alignment”. J Comput Biol 13 (7): 1323–1339. doi:10.1089/cmb.2006.13.1323. PMID 17037961.
- ^ a b c Mount DM. (2004). Bioinformatics: Sequence and Genome Analysis 2nd ed. Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY.
- ^ Higgins DG, Sharp PM (1988). “CLUSTAL: a package for performing multiple sequence alignment on a microcomputer”. Gene 73 (1): 237–244. doi:10.1016/0378-1119(88)90330-7. PMID 3243435.
- ^ Thompson JD, Higgins DG, Gibson TJ (1994). “CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice”. Nucleic Acids Res 22 (22): 4673–4680. doi:10.1093/nar/22.22.4673. PMC: 308517. PMID 7984417.
- ^ Notredame C, Higgins DG, Heringa J (2000). “T-Coffee: A novel method for fast and accurate multiple sequence alignment”. J Mol Biol 302 (1): 205–217. doi:10.1006/jmbi.2000.4042. PMID 10964570.
- 多重整列のページへのリンク
