研究上の成果
研究の初期段階においては、与えられた系統樹の尤度を計算するための方程式 の構造を、そのままKL1のコーディングに置き換えたが、この結果得られた結 果は、きわめて悲観的なものだった。次に再帰的に尤度を計算するアルゴリズ ムに検討を加え、再帰的な計算の途中で生じる中間結果をベクターとして保存 するようにしたところ、劇的な高速化を達成できた。ここでは、論理型言語の 実際のコーディング過程において、枝長の最適化アルゴリズムの論理的構造が きわめて明瞭に提示されたため、方程式のレベルでは埋没していた計算の冗長 性を自然に指摘することができた。る論理型言語の優位性と考えられる。
尤度曲面の変化の様子を視覚化するためのプログラムcontour/1を PIMOS 上に実装した。このソフトウェアを用いると、系統樹の任意の2本の枝 を少しずつ変化させたとき、尤度曲面がどのような振る舞いをするかを直感的 に観察することができる。尤度曲面が単峰性であるという保証はどこにもなく、 尤度を最大にするような枝長の最適化アルゴリズムが誤った結論を導く可能性 を否定できない。実は、最尤法の考え方は、未解決の問題を含んでおり、任意 のデータに対して盲目的に適用してよいというものではない。最終的に得られ た結果に疑問の余地がある場合、coutour/1はあるデータに対応した 尤度曲面を振る舞いを調べるための道具として活用できる。いずれにせよ、将 来的には尤度という尺度そのものに理論的な裏付けを与えることは必要である。
contour/1により、PIMOS上で負荷分散の実験を行った。用いたハー ドウェアはPIM/m (64PE)およびPIM/p (128PE)である。データは人工的に生成 した塩基配列で、このデータがどのような系統樹を導くかはあらかじめ別の手 法(最大節約法)で推定してある。
大きな固まりとしてタスクを扱う場合と、タスクを細切れにして処理させる場 合の効率であるが、これにプロセッサの数とデータ量という要素を加味した場 合、処理時間にどのような差が生まれるだろうか。この様子をグラフにしたの が図1である。
このグラフから直ちにわかることは、データ数が極端に少ない(プロセッサ数 以下である)場合を除いて、前者の大きな固まりとしてタスクを扱う場合の方 が効率が良いということである。これはメッセージパッシングのコストが、プ ロセッサをアイドリングさせるよりも高くつくことを示唆している。ただし、 ここでの尤度の計算においては、2本の枝の長さ以外まったく同一のデータを 各プロセッサが処理していることを考慮すべきである。換言すれば、この場合 プロセッサ毎の処理時間には、大した差はないのかもしれない。
traverse/3、1回目の枝長の最適化で、ほぼ最大尤度を得ることがで きる。むしろ、2回目以降は微々たる改良でしかない。現在のアルゴリズムで は、改良された尤度の差を見て探索の打ち切りを決めているのだが、この1回 目の改良された尤度の値を見て、これ以降の処理を続けるかどうかを判断でき るかもしれない。ただし、この方法で必ず最尤系統樹を得られるという保証は どこにもない。多くの系統樹を吟味し、1回目の改良で得られた尤度と真の尤 度との間の関係を統計的に検証する必要がある。また、トポロジーに無理のあ る系統樹の尤度はなかなか改良されないと予想できる。つまりこのような系統 樹の尤度曲面は、きわめて「平坦」となる。このことが統計的に有意であるこ とを示せれば、改良のための繰り返し回数は、処理の打ち切りのためのよい指 標となろう。
topology/2は、traverse/3に与えるためのトポロジーを生 成する。現時点では、完全探索のための仮説空間生成を生成でき、完全探索が 原理的に可能である。
ソフトウェアとしての成果
ソフトウェア構成の概要
ソフトウェアの構成図を図2に示す。
アピールすべき点
進行状況
contour/1, traverse/3 ver.1.0は基本的な機能はすでに 実現している。
contour/1は現在塩基配列のみしか扱えないが、 traverse/3 ver.1.0はアミノ酸配列を扱うことが可能である。最も 大きな問題は処理速度で、特にtopology/2 ver.1.0は、実用的な運 用をするためには、少なくとも3倍から5倍の高速化が必要である。 topology/2については、無条件にすべてのトポロジー空間を生成す るアルゴリズムが完成している。トポロジーはネストしたリストで表現される が、実際の処理ではノードを両端に持つような枝の集合として扱われる。ネス トしたリストを枝の集合に変換するプログラムがc2b/2である。入力 データ(イプシロン、デルタ、サイトの数、配列、トポロジーと枝長の初期値、 探索打ち切りのための閾値)は一定のフォーマットで、PROLOG的なtermとして 与えられる。配列データを標準入力から読み込み、上述のフォーマットに整形 するプログラムがget_seq/3である。
今後の展開
PIMOSでの実験の結果が思わしくなかったので、今後は基本的にワークステー ションをクラスタリングすることで並列処理を行うよう方針を変更した。 traverse/3 ver.1.0のPVM上での動作を確認したが、効率に関する 実験はまだ行っていない。現在、2台のワークステーション(FUJITSU S-4/20L+Solaris 2.3およびFUJITSU S-4/20L+Solaris 2.4 )をイーサネットで 接続したきわめてプリミティブな環境を用いている。近々、Macintosh(Power PC搭載機と68K搭載機の混成)、DOS/Vマシン、そして並列計算機にPVMと分散 KLICをインストールする予定である。図3に 現時点でのtraverse/3 ver.1.0の実行の様子を示す。画面はXPVMで ある。
トポロジーの探索の方法は、距離行列法との組合せにより行うのが有望だろう。 探索の打ち切り基準はあらかじめ与えるのではなく、探索の優先順位だけをな んらかの方法で導いておいて、処理時間の上限を用いるのが現実的かもしれな い。
上記2つの成果についての自己評価
万能なデータ解析プログラムなど存在しない。特に分子進化系統樹の推定プロ グラムの場合は、現実問題として結果の検証が困難なので、より注意深い使用 が必要である。本プログラムの当初のポリシーは、できるだけ単純で明快なソー スコードを使用者に提供し、使用者はプログラムをブラックボックスとして用 いるのではなく、ある程度プログラムを理解した上でデータ解析を行うという ものだった。しかし高速化のための版を重ねるにつれ、プログラムは徐々に複 雑になりつつある。しかしながら、論理型言語の使用は明らかにソースコード の単純化に寄与している。
この種のソフトウェアをデータ解析のための道具とみなしたとき、すでに開発 済みのソフトウェアとの比較を避けるわけにはゆかない。その多くは、研究の 現場での厳しい要求を反映し、洗練されたものとなっている。特に高速化に関 しては、極限まで努力が払われていると言ってよい。しかしながら本ソフトウェ アのような論理型言語によるアプローチを試みたものはまだなく、その意味で 本研究は特異な位置を占めると言える。