大規模ゲノム情報の高度な検索・比較に関する基礎技術開発とデータマイニングへの応用

大规模基因组信息高级搜索、比对基础技术开发及其在数据挖掘中的应用

基本信息

批准号：
17018023
负责人：
柳浦睦憲
金额：
$ 2.3万
依托单位：
Nagoya University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2005
资助国家：
日本
起止时间：
2005 至无数据
项目状态：
已结题

项目摘要

ゲノム研究に関わるデータは巨大なものが多い.ゲノム自身が巨大な文字列データであることをはじめ,遺伝子やたんぱく質,生物種など,多くの項目を持つデータがある.また,マイクロアレイ技術の発達により,多くの実験を短時間で行えるようになったことも,実験結果のデータを巨大化させている.これら巨大なデータベースを解析し,全体的な特徴の観察や、類似する項目の発見・グループ分け(類似検索・クラスタリング),確からしいルール・特徴ある部分構造の発見(ルール/データマイニング)を行うことは,ゲノム研究において非常に重要な位置を占める.しかし,データが巨大であるため,従来の素朴な方法では計算に莫大な時間がかかる.しかし,この種の問題では,出力する解の数は全ての組合せよりはるかに小さいことが多い.類似する項目を例に挙げれば,一つの項目は他の高々数個の項目とのみ類似する場合が多い.そもそも,非常に多くの項目が類似するようなデータベースは,類似する項目を全て列挙すること自体に意味がない.全ての項目を総当りで比較するのではなく,効率良く類似する可能性のあるペアだけを絞り込むことができれば,極めて短時間で計算を終了することが可能である.本研究班では,ゲノム情報学に現れる基礎的なデータベース解析問題や最適化問題に対して,精度が高くかつ高速なアルゴリズムを開発することとその解析を目指して研究を行った.具体的には、トランザグションデータあるいは各項目が正負のみをとるデータが与えられたとき,その中から真である項目の多くに当てはまるが偽である項目にはほとんど当てはまらないようなパターンの列挙を考え,確率的解析を通して生成されたパターンの信頼性に対する指針を与えた.また,トランザクションデータベースから頻出集合を見つける問題や,文字列データの中から頻出する極大モチーフを全て発見する問題に対して効率良いアルゴリズムを開発した.

基因组研究中涉及的许多数据都是巨大的。除了基因组本身是巨大的弦数据之外，还有许多项目，例如基因，蛋白质和物种。此外，由于微阵列技术的发展，可以在短时间内进行许多实验，从而使实验结果的数据更加巨大。分析了这些巨大的数据库，并观察到整体特征，发现和分组相似的项目（相似的搜索和聚类），依此类推。发现规则和独特的子结构（规则/数据挖掘）在基因组研究中处于非常重要的地位。但是，由于数据是巨大的，因此传统的天真方法需要大量时间来计算。但是，在这种类型的问题中，要输出的解决方案的数量通常比所有组合都小得多。以类似的项目为例，一个项目通常与其他几个项目相似。首先，大量项目相似。对于数据库，列举所有类似的项目是没有意义的。如果只能有效地缩小可能只有相似的对，就可以在很短的时间内完成计算，而是在很短的时间内完成计算，而是在很短的时间内完成计算。该研究团队进行了研究，目的是为基本数据库分析和基因组信息学中出现的基本数据库分析和优化问题开发高精度和快速算法。具体而言，当将数据提供给事务数据或仅积极和负面的数据时，人们认为，适用于许多项目的模式的枚举，这些模式适用于真实的项目，但很少适用于虚假项目，并为通过概率分析生成的模式的可靠性提供了指南。此外，我们为查找从事务数据库中经常发生的集合以及发现字符串数据中经常出现的所有最大图案的问题开发了有效的算法。