カオスダイナミクスに基づく組み合わせ最適化技法を用いた配列モチーフ解析

点击翻译按钮获取中文摘要

ゲノム情報解析技術の急速な発展により,生命を記述する膨大な量の遺伝情報が解読されつつある.どのような情報が遺伝子のどの位置に埋め込まれているかを解析する技術の開発が急務である.この中でも特に,DNAからのモチーフ抽出は,蛋白質の機能・構造の推定に関する知見を与える重要課題である.本研究は,研究代表者らが既にその有効性生を十分に示してきたカオスダイナミクスを用いた組み合わせ最適化技法を用いて,モチーフ抽出問題に関する効果的な解法を実現する.その際,提案アルゴリズムを配列モチーフ解析問題に適した形に改良し,それをハードウェアとして実装することにより,大量の配列モチーフ解析を高速実行できる解析装置のコア部分の開発に繋げることが眼目である.本年度は,公募班として一年目であるため,以下の課題を中心に検討した.1.ギプスサンプラの改良による抽出技法の開発モチーフ抽出の従来技法の一つにギプスサンプリング法がある.この手法は,対象となる塩基配列中のモチーフ候補群から推定される尤度に比例した確率分布により,モチーフ候補を更新する手法であり,従来技法の中でも最も強力な手法の一つであるとされている.提案技法では,推定された尤度に基づいて決定論的に抽出を行うが,その際に生じる局所最適解への収束という問題を,タブーサーチ法の導入により解決を図るものである.大量の数値実験に基づく解析の結果,ギプスサンプリング法を充分に凌駕する手法であることが分かった.2.新しいタブーサーチアルゴリズムによる抽出技法の開発モチーフ抽出問題にタブー・サーチ法を適用する場合に,探索過程において不要な振動が発生することがある.そこで,探索履歴をタブーとする時間を強制的に遅延させることによる探索過程の多様化を実現する新しいタブーサーチ法を提案した.大量の数値実験に基づく解析の結果,ワーストケースにおいても従来の単純なタブーサーチ法の性能を充分に上回る性能を有することが示された.