タンパク質の配列解析プログラム

えられており、ネットワーク上で、左上から右下への矢のスコアの総計を最大に
する経路を探索するのである。この例では、黒丸のノードを通る矢の経路が最適
であり、その経路が、最適アライメントに対応している。矢のスコアには比較さ
れる文字、または文字群の間の類似度が反映されている。タンパク質配列のアラ
イメントの場合、スコアにはDayhoffの数値テーブルが最も一般的に使用されて
いる。これは、アミノ酸の突然変異率を統計的に解析した結果から得られた。




図 1: ２次元 DP の処理 


理論的にはN次元のDPを用いることで、N組の配列群問の最適なアライメ
ントが得られるのであるが、配列群の数が増えると指数的に計算量が増大する。
現在でも、3組を越える配列群問のアライメントに対しては、現実的に計算機上
での実行が困難である。従来から、生物分野の研究者は、アライメントされた配
列群を結合することでマルチプルアライメントを作成してきた。ツリーべ一ス法
と呼ばれる従来の典型的な方法は、2次元DPを用いて、似ている配列から順に、
次々と並べ合わせていくというものであった。
この従来のアルゴリズムは短時間で実行が済むのだが、結果のアライメントは、
質という面では十分ではなかった。そこで、マルチプルアライメントは多くの場
合、熟練した研究者によって人手で行われている。今日でも、たくさんの配列を
アライメントするのは、研究者にとって非常に大きな負荷となっている。

並列反復改善法によるマルチプルアライメント

我々は、計算機による高品質の解を高速に算出する、並列反復改善法を用いた
アライメントシステムを開発した。この並列改善法のアルゴリズムは、反復改善
法をもとにしている。まず最初に、この反復改善法について解説し、その後、我
々の並列反復改善法について説明する。
反復改善法では、次のような反復戦略(図2)を採っている。まず、初期状態
にある配列群をランダムに2つのグループに分割する。そして、2次元DPを用
いて、分割されたグループ間でのアライメントを行う。こうして得られた結果を、


					- 59 -