| 平成８年度 委託研究ソフトウェアの提案 |
国立遺伝学研究所と北陸先端科学技術大学院大学で研究チームを構成し，それぞれの研究機関における並列マシン環境と，国立遺伝学研究所の進化系統樹研究に関するノウハウの蓄積および遺伝子データベースを最大限に利用し，電子メールによるコミュニケーションをもとに緊密な連絡をとりあって共同研究を行なう。
［研究内容］
遺伝子系統樹を作成するというのは，進化学のみならず，現代生物学にとって重要な課題である。最尤法を用いた分子進化系統樹作成法はロバストであり，今まで扱いにくかった遺伝子データの解析手法として期待されている。本研究では，KL1/KLICを用いて最尤法の並列環境への実装を行ない，現実的な遺伝情報解析プログラムの実現をめざしている。これまで，アミノ酸データを扱える最尤法による分子進化系統樹作成プログラムが並列環境に実装された例はまだない。本プログラムはDNA，アミノ酸両データを扱える。大規模なデータ（アミノ酸なら数百残基のデータが数十配列程度）を実用的な時間内で処理できるようにすることが目的である。また，予備実験によりPIM/m上で64PE当たり約35倍の台数効果を達成しているが，同程度の台数効果を一般的な分散環境においてもめざす。
恣意的に仮説空間を生成した場合，ほとんど無意味な探索に膨大な時間を割かねばならない。今後の課題はいかに最尤系統樹の候補を絞り込み，探索空間を縮小するかである。その方法のひとつは，最尤法と距離行列法と組み合わせ，両者の短所を補い合うアルゴリズムを考案・実装することである。
最尤法の計算量の問題を緩和する方法のひとつは，最尤系統樹推定アルゴリズムの並列環境への実装である。本研究では，新世代コンピューター開発機構で開発した並列論理型言語KL1/KLICを用いて，最尤系統樹推定モジュール・DeepForestを作成する。使用する計算機環境は，UNIXマシンである。また，UNIXベースの超並列マシンを使用することも考慮に入れている。
樹形空間はきわめて膨大であるので，完全探索は現在の計算機技術をもってしては不可能である。仮説空間を縮小するためのヒューリスティックスとしては，簡単な樹形に次々に新しい枝をつけ加えてゆく方法や，星型系統樹を用いる枝長空間の探索を捨てて，樹形空間の完全探索のみを行なう方法も提案されている。本研究では，距離行列法である種のガイドツリーを作成しておき，必要な部分（サブツリー）だけについてローカルな完全探索を行なうという新しい方法を提案する。
本研究では，現実のデータから進化モデルを推定するための枠組みとして，並列環境における最尤法の有効性を確認する。さらに複雑かつ多様な大量データを効率的に処理する言語としてのKL1/KLICの有効性を検証する。
○距離行列法によりガイドツリーを作成し，それをもとに不安定なサブツリーを選択した上で完全探索する述語を記述する。
○モデルツリーを用いたシミュレーションを行ない，アルゴリズムの正当性及び有効性を確認する。
○分散環境で高速に大量のデータを処理できるようプログラムの修正・改良を行なう。
○マニュアル及びドキュメントの作成を行なう。
最尤分子系統樹推定ソフトウェア " "DeepForest"
最尤法と距離行列法を組み合わせて，多本数の塩基配列データまたはアミノ酸配列データから，並列・分散環境で高速に可能な樹形を探索し，しかも信頼のおける遺伝子系統樹を復元できる。
ソフトウェアはその機能単位ごとにモジュールに分割されている。モジュールはさらにいくつかのpublic な述語群からなり，これらは他の述語から参照可能である。これらのモジュールを用いれば，最小限の労力でユーザーは新しい構成のソフトウェアを記述することができる。
複数の置換行列のいずれかを選択できる。
なんらかの理由でプログラムの実行が中断された場合に備えて，中間結果を一時ファイルに保存しておき，そこから再スタートできるようなレジューム機能を持つ。
どのサブツリーにどの程度の優先順位を与えるかは非決定論的なものである。プログラムの実行は実行時間の上限で打ち切られる。ユーザは特に詳しく探索したいサブツリーを指定することができる。
ソフトウェア "DeepForest"は，大きくわけて，以下の6つのモジュールからなる。
1.モジュール・treeは，樹形空間（仮説空間）を生成したり，樹形を操作したりするための述語群からなる。
2.モジュール・njは，距離行列を作成したり，近隣結合系統樹を作成したりする述語群からなる。
3. モジュール・stringは，特殊な文字列操作を行なうための述語群からなる。
4. モジュール・listは，特殊なリスト操作を行なうための述語群からなる。
5. モジュール・termioは，項の入出力を行なう述語群からなる。
6.モジュール・traverseは，系統樹のすべての枝を横断的に変化させることにより，最尤値を与えるような枝長の組み合わせを探索する述語からなる。
本プログラムは，klicでコンパイルされることを前提に書かれている。また，入力データは正しく多重整列されている必要がある。したがって，多重整列プログラムaedit やparallel iterative aligner と関連がある。
使用言語は，KL1であり，コンパイラはklicである。
動作環境は，基本的に Sun SPARCstation もしくは Sun SPARCstation 相当の環境を前提としているが，klic の実装してある環境なら、原理的に動作は可能である。ただし、分散環境の klic を実装するためにはPVM が必要である。
対象とする利用者は，配列データから分子進化学的解析を行なう，分子進化学者，分子生物学者，生化学者などである。本プログラムの並列実行は，現時点ではPVM環境下での分散版KLICの実装を前提としている。高速な計算が要求される場合には本プログラムは超並列計算機などの計算サーバに実装されるのが望ましいが，小規模なデータならシングルプロセッサのワークステーションやPCでの利用も可能である。
本ソフトウェアを利用するには，遺伝情報データベースから採取したアミノ酸配列データもしくはDNA配列データを用いる。なんらかの多重整列プログラム（例えば，aeditやCLUSTALW）で配列データを多重整列（マルチプルアラインメント）し，この結果を入力データとして用いる。入力用標準フォーマットへの整形は，ユーティリティ・プログラムを用いる。距離行列法では過小評価する可能性のある変異の大きな配列間の，信頼性の高い進化的距離の推定が可能である。セールスポイントは以下の通り。
1.最尤法と距離行列法を組み合わせて，多本数の塩基配列データまたはアミノ酸配列データから，並列・分散環境で高速に可能な樹形を探索し，しかも信頼のおける遺伝子系統樹を復元できる。
2.ソフトウェアはその機能単位ごとにモジュールに分割されている。モジュールはさらにいくつかのpublicな述語群からなり，これらは他の述語から参照可能である。これらのモジュールを用いれば，最小限の労力でユーザーは新しい構成のソフトウェアを記述することができる。
3. 複数の置換行列のいずれかを選択できる。
4.なんらかの理由でプログラムの実行が中断された場合に備えて，中間結果を一時ファイルに保存しておき，そこから再スタートできるようなレジューム機能を持つ。
5.どのサブツリーにどの程度の優先順位を与えるかは非決定論的なもので，プログラムの実行は実行時間の上限で打ち切られる。ユーザは特にくわしく探索したいサブツリーを指定することができる。
www-admin@icot.or.jp