Abstract

進化系統樹の推定では最尤法を用いた手法が最も優れた推定法の1つとされているが、最尤法の計算量は大きく、種の個数が増えると系統樹の個数は莫大となるため全系統樹の尤度を求めることは事実上不可能となる。系統樹の構成要素であるスプリットの尤度を最尤法によって計算し、スプリットの尤度を用いた行列計算によって系統樹の尤度を近似計算する手法が提案されている。しかし、種の個数がさらに増大すると、近似計算であってもすべての系統樹に対して行うことは困難になる。本研究では、系統樹の推定を系統樹空間における探索問題とみなし、最適化手法を適用することで、近似計算の対象となる系統樹の個数を削減する。また、グリッドミドルウェアを用いたマスタ・ワーカ方式を採用し、尤度計算および最適化手法の並列実行を可能にした。生物9種の系統樹推定において16ワーカを用いた結果、64.0倍の性能向上が得られた。