[P-155]巨大系統樹の推定のために：最節約法に基づくスタイナー樹の高速計算アルゴリズム

発表者（所属）	三中信宏（農環研）
要旨	系統推定に用いられる形質データのサイズがますます巨大化する傾向が強まってきた．形質数だけでなく，端点（OTU）の数が増大するとともに，最節約法や最尤法のような最適性基準（目的関数）による系統樹の離散最適化を行なう手法では，いかにして効率的にかつ高速に最適系統樹を計算するかという問題がつねに直面することになる．とりわけ，計算複雑性の点でもはや完全探索が不可能である以上，発見的探索のためのアルゴリズムを高速化する必要がある．いま開発を進めている系統スタイナー樹アルゴリズム〈Bogen〉は，端点数１万個に達するケースにも対応できるように，許容し得る計算時間内で最節約系統樹を探索するアルゴリズムである．今回は，このアルゴリズムを紹介し，巨大系統樹計算について論じる．