ヘテロな検索空間に対する最適パターン探索アルゴリズムの構築とゲノムデータへの適用

異なる生物種間に対する,配列,制御ネットワーク,相互作用ネットワークなどにおける比較が,新たな知識を得る手法として非常に有効であることが様々な研究事例から明らかとなってきた.そこで,本研究の研究対象である「ヘテロな検索空間に対する最適パターン探索問題」を,系統樹情報を利用した問題に特化して研究を展開している.本年度は,次の成果を得ることができた.まず,前年度に得た成果の一つは,シングル・モチーフを複数個組み合わせた構造化(struotured)モチーフを探索するアルゴリズムの設計,解析,実装,そして予備実験と性能評価を行うことにより,「系統発生フットプリンティングに基づく高速な構造化モチーフ発見アルゴリズム」を提示したことである.そして,昨年度の報告書において,今後の課題を「シングル・モチーフや複数の構造モチーフのなかから効率よく最適解を見つけ出す手法の開発」としていたが,これを次のような形で解決することができた.入カデータによっては,提案した「系統発生フットプリンティングに基づく高速な構造化モチーフ発見アルゴリズム」は大量の解を出力する.さらに,その多くは偽陽性の解と考えられる.このような解のなかから生物学的に正しそうに思える解を抽出するために,解に対する進化確率モデルに基づく対数尤度スコアを導入した.これにより解を一意かつほぼ唯一に順序付けすることが可能となった.さらに,このスコアは,長さなどの構造化モチーフモデルのパラメータが異なっても統一的に使用可能であるという特徴を持っているので,モデルが異なる構造化モチーフの直接比較が可能となった.つまり,本研究の課題である「複数のパターンモデルからなるヘテロな検索空間を対象とする検索方法の構築」を,パターンモデルに直接依存しない対数尤度スコアを導入することにより解決したと言える.更に,Saccharomyoes属の生物種4種を用いた計算機実験を実施して提案アルゴリズムの実用性を,.アルゴリズムの高速性と解の精度を中心に,確認している.実際に非常に高速に計算ができるため,様々な構造化モチーフモデルを一度に比較することが可能であり,様々な入カデータに対する最適なモデルとパターンの同定に成功している.

異なる生物種間に対する,配列,制御ネットワーク,相互作用ネットワークなどにおける比較が,新たな知識を得る手法として非常に有効であることが様々な研究事例から明らかとなってきた.そこで,本研究の研究対象である「ヘテロな検索空間に対する最適パターン探索問題」を,系統樹情報を利用した問題に特化して研究を展開している.本年度は,次の成果を得ることができた.まず,前年度に得た成果の一つは,シングル・モチーフを複数個組み合わせた構造化(struotured)モチーフを探索するアルゴリズムの設計,解析,実装,そして予備実験と性能評価を行うことにより,「系統発生フットプリンティングに基づく高速な構造化モチーフ発見アルゴリズム」を提示したことである.そして,昨年度の報告書において,今後の課題を「シングル・モチーフや複数の構造モチーフのなかから効率よく最適解を見つけ出す手法の開発」としていたが,これを次のような形で解決することができた.入カデータによっては,提案した「系統発生フットプリンティングに基づく高速な構造化モチーフ発見アルゴリズム」は大量の解を出力する.さらに,その多くは偽陽性の解と考えられる.このような解のなかから生物学的に正しそうに思える解を抽出するために,解に対する進化確率モデルに基づく対数尤度スコアを導入した.これにより解を一意かつほぼ唯一に順序付けすることが可能となった.さらに,このスコアは,長さなどの構造化モチーフモデルのパラメータが異なっても統一的に使用可能であるという特徴を持っているので,モデルが異なる構造化モチーフの直接比較が可能となった.つまり,本研究の課題である「複数のパターンモデルからなるヘテロな検索空間を対象とする検索方法の構築」を,パターンモデルに直接依存しない対数尤度スコアを導入することにより解決したと言える.更に,Saccharomyoes属の生物種4種を用いた計算機実験を実施して提案アルゴリズムの実用性を,.アルゴリズムの高速性と解の精度を中心に,確認している.実際に非常に高速に計算ができるため,様々な構造化モチーフモデルを一度に比較することが可能であり,様々な入カデータに対する最適なモデルとパターンの同定に成功している.