A^*アルゴリズムを適用した並列反復改善法によるマルチプルアライメント

スポンサーリンク

概要

論文の詳細を見る
DNA配列やタンパク質のアミノ酸配列の相同性解析に使われるマルチプルアライメントは、分子生物学の様々な分野で利用される重要な処理である。実用的なマルチプルアライメントの課題を計算機で解くには、膨大な計算書を必要とするため、アライメントの品質と計算時間との間にトレードオフの関係が存在している。従来、種々の戦略に基づく多くの方法が提案されてきたが、その品質と計算時間には共に限界があった。我々は新しい戦略として反復改善法を拡張し、最良優先探索の効率的な近似化を図った上で、それをPVMライブラリを用いて並列実装した。さらに、A^*アルゴリズムを適用して探索空間の効率的な刈り込みを実現した。これらの改良の結果、従来法よりも品質のよい、生物学的にも十分意味のあるマルチプルアライメントを、現実的な計算時間内で得ることを可能とした。
社団法人情報処理学会の論文
1997-08-19

著者

関連論文

もっと見る

スポンサーリンク