平成7年度 委託研究ソフトウェアの提案

(16) 並列論理型言語を用いた最尤法による分子進化系統樹作成プログラムに関する研究

研究代表者:國藤 進 教授
      北陸先端科学技術大学院大学 情報科学研究科




[目次]

  1. 研究の背景
  2. 研究の目的
  3. 研究の内容
  4. ソフトウェア成果


[研究の背景]

生物進化の根本は,自己複製をくりかえす遺伝子DNAが突然変異を蓄積して 少しずつ変化してゆくことである。このプロセスは,30億年以上前の生命の 誕生以来,連綿として続いてきている。遺伝子が親から子,子から孫へと確実 に伝えられてゆく性質を利用して,それぞれの遺伝子の系統関係を解き明かす ことができる。これを遺伝子系統樹と呼ぶ。遺伝子系統樹は,生物進化の基本 記述子である。

同じ生物種内には多数の個体が存在するが,それらの中では,同一種類の遺伝 子といっても,個体によって微妙に塩基配列が異なっている。このため,同一 の遺伝子でも,生物種ごとに多個体の遺伝子系統樹(遺伝子系図と呼ぶことが 多い)を作成することがよく行なわれる。もっとも多く研究されているのは, ミトコンドリアDNAであり,ヒトではすでにミトコンドリアDNA(約50 0塩基の領域)が1000人以上で調べられている。

ひとつの生物を構成しているすべての遺伝子セットの最小単位を「ゲノム」と 呼ぶが,ヒトゲノムの場合,約30億個の塩基からなりたっている。このなか には,約7万〜8万個の遺伝子が含まれると推定されている。したがって,潜 在的な遺伝子系統樹の種類数は数万個にのぼる。

このように,遺伝子系統樹を作成するというのは,進化学のみならず,現代生 物学にとって重要な課題である。しかしながら、実際の分子系統樹の可能な樹 形数は,比較する配列を増やしてゆくと急速に増加する。例えば、n本の配列 に対して可能な無根系統樹の樹形数は,(2n - 5)! / [2(n-3)乗× (n - 3)!] である。従って、このような組み合わせ爆発を克服し、実際の遺伝情報データ ベースのデータに適用可能なアルゴリズムを構築することが重要である。

分子進化系統樹の作成法には、大きくわけてふたつのカテゴリーが存在する。 ひとつが距離行列法であり、もうひとつが形質状態法の一種である最尤法であ る。本研究は信頼性は高いが非常に高い計算コストの点で見捨てられていた最 尤法に焦点をあて、その並列環境上での実装を考える。その際、信頼性は乏し いが経験的アプローチで高速推論可能な距離行列法の融合を考え、実際の遺伝 情報データに対して適用可能にする。


[研究の目的]

遺伝子系統樹を作成するというのは,進化学のみならず,現代生物学にとっ て重要な課題である。分子進化系統樹の作成法には、大きくわけてふたつのカ テゴリーが存在するが、本研究では最尤法に焦点をあてる。

最尤法を用いた分子進化系統樹作成法は、他の方法に比較してロバストネス が高く、今まで扱いにくかった遺伝子データの解析手法として期待されている。 しかし、この方法は非常に高い計算コストを要求するため、実際のデータ解析 に使われることは少なかった。本研究では、KL1/KLICを用い、この方法の並列 マシンへの実装を行い、現実的な遺伝情報解析プログラムの実現を目指してい る。今まで、アミノ酸データを扱える、最尤法による分子進化系統樹作成プロ グラムが並列環境に実装された例はほとんどないが、本プログラムはDNA、ア ミノ酸両データを扱うことが可能である。現在、予備実験により、PIM/m上で 64PE当たり約35倍の台数効果を達成している。

もし全く恣意的に仮説空間を生成した場合、ほとんど無意味な探索に膨大な 時間を割かねばならない。今後の課題はいかに最尤系統樹の候補を絞り込み、 探索空間を縮小するかである。その方法のひとつは、積極的に距離行列法と組 み合わせることにより、両者の短所を補い合うアルゴリズムを構築することで あろう。二つ目の課題は、本プログラムがサーバマシン上で動作する可能性が 高いことから、系統樹というグラフィカルな情報を扱うための、適切なユーザ インターフェースをいかに提供するかということである。これ以外にも、マル チプルアラインメントやアミノ酸置換行列の推定を分子進化系統樹作成アルゴ リズムに取り込むことなど課題は山積みしているが、上に述べた二つの点が当 面の重点課題となる。


[研究の内容]

研究の背景(3)や目的(4)で述べたように、DNAやアミノ酸配列データのよう な遺伝情報データの急激な増加にともない、より信頼のおける分子進化系統樹 推定法の開発が待たれている。最尤法は、原理的に遺伝子データの持つ情報を 効率的に利用できるため、信頼性が高いとされており、これからの系統樹作成 方法の枠組を与える可能性を持っている。しかし、その一方で膨大な計算コス トを必要とするために、今まで敬遠されるきらいがあった。本研究では、この 計算コストにおける困難さを緩和することを念頭に置いて、最尤法を並列環境 に並列論理型言語を用いて実装するための基礎的な研究を踏まえ、更に実用的 な系統樹作成システムの開発を行う。

分子進化系統樹とは、生命がいかに進化してきたかを分子レベルで表現した 系統樹である。古典的な意味での系統樹は、生物の表現型(つまり形態)の変 化を化石資料などをもとに推定して得られたものであった。したがって、この 方法論には、基準となるべき客観的な尺度が必ずしもあるわけではなかった。 一方、分子生物学の発展にともない、我々は生命の設計図である遺伝情報を容 易に手に入れることができるようになった。この離散的な遺伝情報をもとに生 命の進化を分子レベルで調べようとする学問が分子進化遺伝学であり、そのた めの強力な表現手段となるのが分子進化系統樹である。

分子進化系統樹の作成法には、大きくわけてふたつのカテゴリーが存在する。 ひとつが距離行列法であり、もうひとつが形質状態法である。

距離行列とはDNAやアミノ酸配列間の遺伝的な距離(推定突然変異数)を行 列にしたものである。距離行列法はこの遺伝的な距離を用いて進化系統樹を推 定する。一般に、距離行列法では、距離行列そのものの計算を非常に簡単にで きるので、高速な推論が可能である。しかし、遺伝情報の持つすべての情報を 使っているわけではないので、進化的な変異が大きくなると誤った結果を導く 可能性がある。

一方、形質状態とは、遺伝情報のつらなり(配列)そのものを指す。形質状 態法では配列の一座位ごとに進化的関係を推定し、これをもとに全体の進化系 統樹を再構成する。特に最尤法は、あからじめ与えた進化モデルと矛盾しない 範囲内で、信頼性の高い系統樹の推定が期待できる。しかし、それとは裏腹に 非常に高い計算コストが要求され、現在のところまだ一般的な方法とは言えな い。

最尤法の計算量の問題を緩和する方法のひとつは、最尤系統樹推定アルゴリ ズムの並列環境への実装であろう。本研究では、新世代コンピューター開発機 構で開発した並列論理型言語KL1/KLICを用いて、最尤系統樹推定プログラム群 go/0(仮名)を作成する。使用する計算機環境は、UNIXワークステーション、 PIMOS(PIM/m)である。UNIXベースの超並列マシンを使用することも考慮に入れ ている。

現段階においては、traverse/3とcontour/1という試作プログラムの開発がほ ぼ終了している。この試作プログラムでは、樹形空間の生成は人手で行わなく てはならない。現実のデータ解析においては、樹形空間(つまり仮説空間)の 生成の自動化を行う必要がある。樹形空間はきわめて膨大であるので、完全探 索は現在の計算機技術をもってしては不可能であると思われる。仮説空間を縮 小するためのヒューリスティックスとしては、簡単な樹形に次々に新しい枝を つけ加えてゆく方法や、星型系統樹を用いる方法がある。特に前者は、枝の交 換と組み合わせることにより、ローカルマシキマムに陥る可能性をある程度排 除することができる。また、枝長空間の探索を捨てて、樹形空間の完全探索の みを行う方法も提案されている。しかし、いずれの方法も最適解を保証してい るわけではない。より根本的で効率的な方法の研究が必要である。上に述べた ように、正しい多重整列やアミノ酸の置換行列の推定方法に関する問題も解決 しなければならない。厳密に言えば、この二つを含めた統合的なシステムの構 築なしには、理想的な進化モデル推定プログラムの実現は不可能であるが、あ まりに膨大な計算量を扱わなければならないことが予想されるので、本研究で は扱わない予定である。

本研究では、現実のデータから進化モデルを推定するための枠組みとして、並 列環境における最尤法の有効性を確認する。このことを第一ステップとして、 複雑かつ多様な大量データを効率的に処理するシステムのインプリメント言語 としてKL1/KLICが有効であることを実証する。


[ソフトウェア成果]

(1)作成されるソフトウェア名称
最尤分子系統樹推定プログラム群``go/0''(仮名)

(2)そのソフトウェアの機能/役割/特徴
最尤法と距離行列法を組み合わせて,多本数の塩基配列データまたはアミノ酸 配列データから,高速に可能な樹形を探索し,しかも信頼のおける遺伝子系統 樹を復元できるアルゴリズムを作成する。次の3種類のプログラムの実装を考 えている。

  1. 樹形空間自動生成プログラムtopology/2は、樹形空間(仮説空間)を自動 生成する。ここで生成する樹形空間は最尤系統樹の候補を含み、しかもできる だけコンパクトな仮説空間でなくてはならない。仮説空間の縮小を行なうため に、ここでは距離行列法を用いることを考えている。つまり、距離行列法で系 統樹の概形を推定した後、その周辺の樹形を優先的に探索する。ただし、この 方法は試作版の結果を見て変更する可能性がある。

  2. 枝長最適化プログラムtraverse/3 は、系統樹のすべての枝を横断的に変 化させることにより、最尤値を与えるような枝長の組み合わせを探索する。別 な言葉で言えば、枝長空間の探索を行うプログラムである。具体的には、もし ある系統樹の樹形を固定した場合、その尤度(もっともらしさの尺度)を決め るのはそれぞれの枝の長さの組み合わせである。もし、それぞれの枝を少しず つ変化させた場合、それにしたがって尤度も少しずつ変化する。枝の数がn本 ならば、これはn次元枝長空間における、最も大きな尤度を与えるようなn変数 の組み合わせの探索問題であると言うことができる。n次元尤度曲面があらゆ る点で微分可能で、しかもただひとつの最大値を持つかどうかは精密に議論さ れているわけではないが、経験的にはこれらの性質は肯定されている。

    このプログラムのプロトタイプである性能評価用試作版についての特徴は以 下のようになっている。

    traverse/3にはver.0.1とver.0.2のふたつの版がある。ver.0.1は基本的で 単純なアルゴリズムを採用し、ver.0.2は高速化のために改良したアルゴリズ ムを採用している。用いる配列の数が多いほど、ver.0.2のver.0.1に対する効 率は際だってくる。配列の数が6のとき、ver.0.2はver.0.1の約320倍の速さで 処理を行うことができる。

    現実のデータを適度な時間内に処理するためには、ver.0.2を用いる必要が あるが、より多くのメモリを消費するので、公開されるtraverse/3はこの点に ついて考慮をする必要がある。

  3. 対数尤度曲面表示プログラムcontour/1は、n次元対数尤度曲面を生成する ことで、ユーザに最尤値を与える点に至るまでの、曲面の変化の様子を知らせ るプログラムである。現実的な問題として、n次元尤度曲面がきわめて平坦で ある場合、いつ探索を打ち切るかを決定することは重要なことである。なぜな ら探索を打ち切るタイミングが少し変わっただけで、枝長が大きく変わってく るかもしれないからである。ユーザーにいつ探索を打ち切るかという判断の材 料を与える方法のひとつは、このn次元尤度曲面の様子を可視化して提供する ことであろう。このためには、高速に枝長に対応した対数尤度を計算する必要 がある。

    また、このプログラムのもう一つの目的は、多量の対数尤度計算を通して、 効果的な負荷分散の方法を見つけることである。contour/1はデータに応じて、 いくつかの並列実行方法のいずれかを選択することができ、その比較が可能で ある。つまりこのプログラムは、疑似的にトポロジー空間の探索の際の負荷分 散の様子を実現しているので、この結果から実際の最尤系統樹探索の効率につ いてある程度の予想を立てることができる。




www-admin@icot.or.jp