ゲノム配列の高次圧縮・索引構築と高次幾何構造解析による知識発見

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

ゲノムデータベースからの知識発見のためのアルゴリズムとデータ構造に関する研究を行った.まず,ゲノム配列データベースからの高速パタン検索のアルゴリズムとデータ構造を開発した.索引としては既存の圧縮接尾辞配列を用いたが,新しいアルゴリズムにより従来の30倍の速度での検索が可能になった.次に,2つの長いゲノム配列のアラインメントを計算するための手法である,MUM(Maximal Unique Match)を列挙する省スペースなアルゴリズムを開発した.配列の長さをnとすると,既存手法ではO(n log n)ビットのスペースが必要であったが,本研究ではこれをO(n)ビットに圧縮した.これにより,ヒトの全DNA配列2つのMUMの計算がメモリ4GBのPC1台を用いて約6時間で計算できた.また,ヒトとマウスの間の共通部分については約24時間で計算できた.データベースからの知識発見のために,データベース中の複数の属性間の最適相関ルールを求める高速アルゴリズムを開発した.最適とは,支持率を固定した場合の最大確信度ルールまたは確信度を固定したときの最大支持率ルールを表す.従来手法では2値属性のみしか効率良く扱えなかったが,本研究の手法では数値属性に対して効率良く動作する.また,数値属性間の最適相関ルールを拡張し,様々な確信度に対する最適領域をピラミッド型の図形で表現する方法を提案し,その効率の良い計算法を提案した.これを最適ピラミッドによる相関ルール表現と呼ぶ.これを用いることでデータベースから抽出した知識を簡潔に表現することができ,過学習の回避もできる.また,ピラミッドを用いてデータの可視化を行うこともできる.