図 4: 各アルゴリズムの性能比較 


さらに、より多くの配列を一度に、実用的な時間内でアライメントすることを
可能にする限定分割手法も、同時に開発した。これは、上記の並列反復改善法を
用いた実験結果を調査し、各反復ごとに選ばれたアライメントがどのように分割
されていたかに注目することで得られた。2つのグループに分割する際に、片方
を少ない本数にすると効果的な改善が行われるのである。この手法を並列反復改
善法に組込むことで、実際に生物分野で扱われるような多くの本数の配列群を同
時に扱っても、高品質なアライメントを妥当な時間内で獲得できる。

デモンストレーション

今回のデモンストレーションでは、並列反復改善法を用いて、一度に22本のア
ミノ酸配列群のアライメントを行う。256の要素プロセッサ(PE)をもつPIM/n
上で実行を行い、約10分で終了する。
なお、分割限定法(今回は、少ない方の配列群を1本、もしくは2本の場合の
みに限定)を適用し、すべての分割に対して、2次元DPを並列に実行するため
に253PEを使用している。また、各反復ごとに最良のアライメントを選択するた
めに1PEを使用しているため、実際には254PEを稼働させている。
このデモンストレーションでは、反復を繰返すたびに、アライメントが改善さ
れてゆく様子がわかりやすく表示される(図5参照)。それぞれの文字は、その
アミノ酸のもつ性質に従って配色を行っている。また、アライメントの下に、各
カラムごとのスコアを棒グラフを用いて図示している。これは、棒が高いほど、
そのカラムに性質の良く似たアミノ酸が並べられていることを意味している。特
に良く似たアミノ酸がたくさん並んでいる部分は、進化の過程において保存され
た部分だと考えられ、タンパク質の構造や機能の点で重要な意味を持つ、配列モ
チーフである可能性が高い。このデモンストレーションの最終結果では、ATPに
結合する機能をもつ配列モチーフを捕えることに成功している。


					- 61 -