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

异构搜索空间最优模式搜索算法的构建及其在基因组数据中的应用

基本信息

批准号：
16700146
负责人：
丸山修
金额：
$ 2.3万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2006
项目状态：
已结题

项目摘要

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

各种研究示例表明，对于不同的生物种类，序列，控制网络，相互作用网络等之间的比较非常有效，作为获得新知识的一种方法。在此财政年度中使用系统树的问题。结合多个单个基础，通过进行初步实验和性能评估。结构序列。尽管有一些形式可以解决此问题此外，其中许多被认为是假阳性的解决方案，以提取似乎是从这种解决方案中提取生物学的溶液，基于该解决方案的演化概率模型，已经引入了对数可能性得分。结果，解决方案几乎可以统一，此外，即使结构化基序的参数（例如长度）也可以统一使用。可以直接比较模型的结构化基序，换句话说，“建立一个由多种模式组成的搜索方法”。进一步取决于模型的评分，通过使用四种糖果属进行计算机实验来实践算法。非常高的速度，因此可以立即比较各种结构化基序模型，并为各种猫的模型和模式进行比较。