概要

タンパク質は20種類のアミノ酸が鎖状に連なってできており、その構造や機
能はアミノ酸の配列から決定される。タンパク質の配列解析は、タンパク質の機
能や構造の予測、またはタンパク質同士の進化的関係の把握を行う上で重要な研
究課題である。我々は並列反復改善法を用いて、配列解析の代表的な問題である
マルチプルアライメントの解決に取り組んでいる。一般に、この種の組合せ最適
化問題を解決するには莫大な計算量が必要であるが、我々の開発した並列反復改
善法によるシステムは、PIM上で実行することによって、生物分野の研究者が実
際に扱う規模の問題を、高速かつ高品質に解決する。

特徴

反復改善法:
部分的な改善を反復的に行い、その結果として、より高品質のアライメント
結果を効果的に得ることを可能とした手法である。

並列実行による速度向上:
組合せ問題における探索木の枝の評価を、多くの要素プロセッサを使って
並列に行うことで、マルチプルアライメントが高速に行える。

探索木の枝刈り:
探索木の枝刈りを効果的に行うヒューリスティクスである、限定分割手法
を導入し、この組合せ問題を現実的な時間内で解決している。





並列反復改善法 

					- 57 -