Multiple Protein Sequence Alignment Using Parallel Iterative Algorithm and A* Algorithm

IPSJ Web Site 2 Citations 23 References

Bibliographic Information

Other Title
  • アミノ酸配列のマルチプルアライメントにおける反復改善過程の並列化とA*アルゴリズムの適用
  • アミノサン ハイレツ ノ マルチプルアライメント ニ オケル ハンプク カイゼン カテイ ノ ヘイレツカ ト A アルゴリズム ノ ソウグウ

Search this article

Description

タンパク質のアミノ酸配列のマルチプルアライメントの問題は，アミノ酸残基の保存や置換,欠失や挿入に一定の指標を与え，その総和（sum-ofLpairs）が最大となるものが最も確からしいアライメントであるというモデル化が現在主流になっている．このモデルは,総和の最大化に関する組み合わせ最適化問題を解くこととなる．大規模の問題を計算機で高精度に解くには,組み合わせの数が爆発するため，ヒューリステイクスの導入が必要となり，アライメントの精度と計算時間との間にトレードオフの関係が存在している．そのため実用的には従来から近似的な解法がとられてきた代表的な近似解法は，ツリーベース法であるが,解の精度は必ずしも十分ではなかった．我々は新しい戦略として反復改善法を拡張し，最良優先探索の効率的な近似化を図った上で,最良優先探索における近傍探索を並列実装した．さらに,Ａ*アルゴリズムを適用して探索空間の効率的な刈り込みを実現した．これらの改良の結果,大規模のマルチプルアライメントの問題を高精度に，現実的な計算時間内で得ることを可能とした．

Since the multiple sequence alignment problem requires enormous calculation time, one is faced with a trade-off between computation time and the quality of alignment. To date, although several approximation methods have been proposed, the quality of alignments produced by previous methods is limited. As a new strategy, we employed an iterative scheme with best-first search, and parallelized its search step. Furthermore we implemented the A* pruning algorithm instead of dynamic programming, to drastically reduce the search space. As a result, our new parallel system enables biologically accurate multiple sequence alignment to be performed within reasonable calculation time.

Journal

Citations (2)*help

See more

References(23)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top