最初の処理に戻して、再び分割から繰り返す。このように、ランダムに2つに分
割されたグループ間での2次元DPを繰返すと、全体のアライメントの質が徐々
に改善されていく。




図 2: 反復改善法のアルゴリズム 




図 3: 反復改善法の並列化アルゴリズム 

この反復改善法では、従来のアルゴリズムで得られるアライメントに比べ、か
なりスコアの高いものを得ることができる。図4における(b)が、実際に7本の
アミノ酸配列を反復改善法でアライメントした際の性能をグラフ化したものであ
る(乱数列を変えて実験を3回行った)。比較のために、ツリーべ一ス法で得ら
れた結果のスコアを水平線(a)で表示している。ただし、配列数が増えると、反
復改善法は収束までに多大な反復回数を要してしまう。
一般に並列計算機を利用することで実行時間の削減を期待できる。我々は以下
に説明する並列反復改善法(図3)を考案した。まず、あらかじめアライメント
された配列群を2つのグループに分割する全組合せを網羅する。そして、それぞ
れの分割に対して、並列に2次元DPを用いてアライメントを行う。こうして得
られた中で最もスコアの良い結果を選び、それを次のアライメントとして処理の
最初に戻して、分割から繰返す。図4の(c)を見ると、実行時間の点、安定して
良い解が得られる点において、反復改善法に比べ、優れていることがわかる。


					- 60 -