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

点击翻译按钮获取中文摘要

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