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

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

基本信息

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

项目摘要

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

从各种研究案例中可以清楚地看出，不同生物物种之间的序列、调控网络、相互作用网络等的比较是获取新知识极其有效的方法。因此，本研究的目标“异构搜索空间的最优搜索空间”我们正在进行“模式搜索问题”的研究，专门研究利用系统发育树信息的问题。今年，我们获得了以下结果。首先，前一年获得的结果之一是：搜索组合多个单一图案的结构化图案。通过设计、分析和实现算法，并进行初步实验和性能评估，我们提出了“基于系统发育足迹的高速结构化主题发现算法”的“单一主题”问题。 “开发一种从多个结构基序中有效找到最佳解决方案的方法”，但这个问题是通过以下方式解决的。根据输入数据，提出了“系统发育足迹法”一种快速结构基序发现算法基于此外，许多这些解决方案被认为是误报。为了从这些解决方案中提取看起来生物学上正确的解决方案，我们基于解决方案的进化概率模型计算对数，引入了唯一且唯一的似然得分。几乎唯一地订购解决方案。此外，该分数具有即使结构化主题模型的参数（例如长度）不同也可以统一使用的特征，因此可以直接将结构化主题与不同模型进行比较。换句话说，这个问题。研究的目的是可以说，通过计算机实验引入不直接依赖于模式模型的对数似然分数，解决了“构建针对由模式模型组成的异构搜索空间的搜索方法”的问题。我们确认了算法的实用性，重点是算法的高速性和求解的准确性。事实上，计算速度非常快，使得可以一次比较各种结构化主题模型，我们已经成功识别了。各种输入数据的最佳模型和模式。