生体内化合物の効率的な比較、探索、発見アルゴリズムの開発

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

比較・探索アルゴリズムに関しては、まず生体内化合物の二次構造を分子グラフとみなしグラフの複雑さの尺度に着目した。特に木幅(tree-width)と全域木の数に注目した。二つの化合物を比較する際に一方の化合物の木幅に上限がありもう一方の化合物の全域木の数が化合物の原子数の高々多項式であるという問題設定において効率的なアルゴリズムを開発した。この結果はInformation Processing Letters誌に投稿・受理された。実際に、生体内化合物の木幅は高々4であり、また全域木の数も次数5程度の多項式で済むことを確かめた。さらに、木幅を生体内化合物の一つの属性とみなした場合に、代謝パスウェイや酵素の分類等の生体内化学反応と木幅の相関関係についても調べ、これらすべての結果をまとめた論文を準備中である。さらに、比較・探索アルゴリズムに関しては、順序なし木とみなした糖鎖の効率的な比較・探索を行うツールKCaMを開発・実装し、京都大学バイオインフォマティクスセンターのKEGG内で糖鎖DB、GLYCAN内の糖鎖比較・探索サービスを開始した。この結果は、NAR誌に投稿・受理された。発見アルゴリズムに関しては、順序木とみなした糖鎖のための確率モデルと効率的なパラメータ推定手法を構築・実装した。この手法は順序木のための最初の確率モデルであり、より一般的なベイジアンネットワークの既存のパラメータ推定手法に較べて提案学習手法ははるかに効率的である。この手法の糖鎖への適用により糖鎖の特徴的なパターンを抽出した結果を含めて、ISMBやSIGMOD Record誌等に投稿し受理された。さらに、代謝パスウェイをマルコフモデルとみなしマイクロアレイデータからパラメータ推定を行い、遺伝子発現の観点から有効な代謝パスを推定する手法を構築し、実データによる検証結果をCSBに投稿・受理された。