様々な最適解探索手法のマルチプルアラインメントへの適用と性能評価(アルゴリズム理論)

概要

論文の詳細を見る
本研究では, バイオインフォマティクスの分野における配列解析の基本的な問題であるマルチプルアラインメントにおいて, 人工知能の分野における様々な最適解探索手法を適用し, 性能評価実験を行う.なお, 適用した手法は, A^*, Enhanced A^*, 反復深化A^*(IDA^*), 再帰的最良優先探索(RBFS), MREC, 段階的節点展開方式(PEA^*)である.MRECは, 15パズルでは, IDA^*と比べわずか1%の状態数しか削減することができず, 有効でないと考えられていたが, 性能評価実験を行った結果, これまでに8配列までしか解くことができなかった延長因子(EF-1α)のマルチプルアラインメントにおいて, MRECは11配列まで解くことに成功し, 少メモリかつ高速に実行できたことを示す.また, これまでに分子生物学の分野で扱われたマルチプルアラインメントを集めたベンチマーク用のデータベースであるBAliBASE (Benchmark Alignment dataBASE)を用いた実験においても, これまでの手法の中で, 最も高速に最も少ないメモリ量で最適解が得られたことを示す.
社団法人電子情報通信学会の論文
2005-04-01