探索アルゴリズムの並列化とその計算量の研究

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

本課題では,探索アルゴリズムの並列化とその計算量について研究を行ない,次の成果を得た.タンパク質や核酸のデータといったゲノムデータを対象とした探索アルゴリズムの開発は宮野(九州大学)等によってその端緒はつけられており,大量ゲノムデータからの知識獲得システムBONSAIとして大きな成功を納めた.しかし,一方では,多種多様なデータを前にして,逐次的手法による探索方式の限界も指摘されている.また,探索の問題は,純粋に理論面からは,C.H.PapadimitriouやM.Yannakakisらによって局所探索の理論が存在するが,様々な探索方式・問題を捉えるためには不十分である.本研究では,知識獲得システムの核となる探索アルゴリズムの並列化による効率化を行ない,多様なデータに対応できる並列知識獲得システムBONSAI Gardenの開発を行なった.知識獲得システムBONSAIは正負2つの例から,その例を説明する仮説をアルファベットインデキシングをラベルとする決定木として出力する.このシステムは単一のデータからなる膜貫通領域やシグナルペプチドといったようなタンパク質の説明に成果をあげた.しかしながら,2つ以上のデータが混在した例では,単一のBONSAIシステムで,意味のある小さな仮説を出力するには限界があった.この問題を解決するために,複数のBONSAIを並列に動かすアルゴリズムを設計し,知識探索の並列化を行なった.BONSAI Gardenと呼ばれるこのシステムでは,特殊なプロセスGardenerにより管理された複数のBONSAIプロセスが並列に動作し,効率のよい解空間の探索を行なう。このシステムによって、当初の目的の複数の小さな仮説を出すことに成功した.さらに,DNAおよびタンパク質の塩基配列を入力とする実験を行ない,核となる並列探索アルゴリズムの実験的有効性を確かめた.