大規模ゲノムデータ処理に対する高速高精度アルゴリズムの開発

开发用于大规模基因组数据处理的高速、高精度算法

基本信息

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

项目摘要

ゲノム研究に関わるデータは巨大なものが多い.全体的な特徴の観察や,類似する項目の発見・グループ分け(類似検索・クラスタリング),確からしいルール・特徴ある部分構造の発見(ルール/データマイニング)を行うことは,ゲノム研究において非常に重要な位置を占める.しかし,データが巨大であるため,従来の素朴な方法では計算に莫大な時間がかかる.全ての項目を総当りで比較するのではなく,効率良く類似する可能性のあるペアだけを絞り込むことができれば,極めて短時間で計算を終了することが可能である.本年度は,ゲノム情報学で基礎的な問題の中から,実験結果の解析に使われるパターンマイニング,最適分類規則発見,配列の決定やアセンブリなどで用いられる相同性の発見アルゴリズムと並び替えを行うアルゴリズムの開発に関して,最適化・アルゴリズム的な技術を適用して改善できる点を見つけ出し,そこに新たな技法を提案した.代表的な成果を以下に挙げる.・与えられたグラフから,クリークに近い構造を全て見つける問題,データベースから多くの項目にあいまいさを許容した意味で含まれる集合を全て見つけ出す問題に対するアルゴリズムを開発した.・ベクトル集合の各要素に真か偽が与えられているデータ集合に対するパターン抽出の基本問題に関する性質を解析した.・集合被覆問題に対する高速近似解法を設計する上で有効な手法を検討し,知見を得た.・DNA解析等で利用される,所定の熱力学的制約を満たしたDNA配列集合を自動的に生成(設計)するアルゴリズムを提案した.

基因组研究中涉及的许多数据都是巨大的。观察总体特征，发现和分组相似的项目（相似的搜索和聚类），发现某些规则和独特的子结构（规则/数据挖掘）在基因组研究中占有非常重要的地位。但是，由于数据是巨大的，因此传统的天真方法需要大量时间来计算。如果您只能有效地缩小可能相似的对，而不是比较违反行中的所有项目，则可以在短时间内完成计算。今年，我们将介绍基因组信息学的基本问题，包括模式挖掘，最佳分类规则发现和同源性发现，这些发现用于实验结果分析以及序列和组装的确定。关于分类算法的开发，我们已经确定了可以通过应用优化和算法技术来改进的领域，并提出了一种新技术。代表性结果如下列出。 - 我们已经开发了一种算法，该算法是从给定图中找到靠近小溪的所有结构的问题，并从某种意义上找到包括许多项目在许多项目中模棱两可的所有集合。 - 我们已经分析了图模式提取的基本问题的属性，其中列出了矢量集的每个元素的数据集。 - 我们研究了设计快速近似解决方案以设置涵盖问题并获得知识的有效方法。 - 我们提出了一种算法，该算法会自动生成（设计）DNA序列集，该序列集满足给定的热力学约束，该序列用于DNA分析，等等。