最適化手法の分子系統樹推定への応用

点击翻译按钮获取中文摘要

分子系統樹の推定において、現在の最尤法の欠点は他の方法に比べて計算時間がかかることである。これは、トポロジーを仮定した系統樹の尤度を計算する際に、最尤なパラメータ(各枝の長さ)をNewton法で最適化する必要があるため計算量が多いことによる。本研究では、最適化手法を用いて、最尤法のこの欠点をある程度まで克服した。まず、各2種間の距離を最尤法で推定しておいて、トポロジーを固定した際に、各枝の長さを、その距離行列に関する最小2乗法を行なって近似的に求めると、その残差平方和の値は最尤法を行なった時の尤度の値と相関が高いことが分かった。従って、このような簡便法で有望であるようなトポロジーを予めスクリーニングしておいて、残差平方和の小さいトポロジーについてのみ、きちんした最尤法で解析を行なうことが有効である。この場合、より正確には枝の長さが正であることを考慮する必要がある。ところが、このような制約をつけた場合の最小2乗法は、正確に解けるものの、制約がない場合に比してかなり計算時間がかかる。そこで、この困難を解決するために、残差平方和を最小化する代わりに残差の絶対偏差和(L1ノルム)を最小化することを考えた。この問題は、線形計画問題に帰着でき、枝の長さが正であるという条件をつけくわえても簡単に解ける。そこで、絶対偏差をスクリーニングに使う評価関数とし、これを正確に最小化するようなトポロジーを見つけ、その後で絶対偏差が小さいいくつかのトポロジーに関して尤度を最大化し、そのなかで最大のものをもっともらしい系統樹であると推定することを考えた。この問題に対し、組合せ最適化についてよく使われる定石の一つである分岐限定法を適用し、効率的なトポロジー探索法を開発した。