局所最適解の回避

樹形探索において局所最適解に陥った場合、それを抜け出す方法（Simulated annealingやMCMCMCなど）と、そもそも陥らないようにする方法（ResamplingやGenetic algorithm）があるがどちらもここでまとめる。

Resampling

再サンプリング法では複数の初期系統樹からbranch swappingによって樹形を探索し、その中で最も高い尤度を持つ樹形を採用する。つまり、探索範囲を広げることで、特定の局所最適解に陥る可能性を低減している。

距離行列法では何度繰り返しても同じ樹形しか得られないが、stepwise additionやstar decompositionでは異なる出力が得られる可能性が高いので、それらをresampling法の初期系統樹に用いることができる。

Tabu searchを組み合わせると、訪れたことのある樹形空間周辺を再訪しないようにすることも可能らしい(Whelan, 2007)。

Resampling: Ratchet

Ratchet法では、初期系統樹を構築する際にデータに撹乱を与え、樹形空間の様々な点から探索を開始する。Ratchetは最節約法に対しての適用が初出であり、Nixon (1999)に記載されている。Likelihood ratchetでは以下の手順で探索を進める。

1. 距離行列法などで初期系統樹を構築する。

2. Branch swappingで樹形探索を行う。局所最適解に陥ってそれ以上尤度の高い樹形が出現しなくなるまで続ける。

3. 塩基/アミノ酸サイトを無作為に加重して距離行列法によって系統樹を再構築する。この無作為加重は塩基/アミノ酸サイトのbootstrap resamplingと同義である。この無作為加重によりtree landscapeが変化し、2.が陥った局所最適解を回避できる可能性が高まると説明されている。

4. 無作為加重を元に戻し、通常のbranch swappingによって樹形探索を始め、局所最適解に到達するまで続ける。

5. 尤度の高い樹形が得られなくなるまで、もしくは設定した探索回数の上限に達するまで3.と4.を繰り返す。

6. 無作為加重→探索を繰り返した回数だけ最尤系統樹が得られるが、その中から最も尤度が高いものを採用する。

右図はVos (2003)から引用した。図ではtree landscapeが変化しているように描かれているが、branch swappingは元のデータを使って進めていくので、どちらかというと探索開始点に摂動を加えるだけで、tree landscapeの変化はないように思う。

Nixon, K. (1999). The Parsimony Ratchet, a New Method for Rapid Parsimony Analysis. Cladistics 15: 407–414.

Vos, R.A. (2003). Accelerated Likelihood Surface Exploration: The Likelihood Ratchet. Syst. Biol. 52: 368–373.

Resampling: Partial stepwise addition (PSA)

PSAではまず、全OTU数に応じて二項分布からランダムに選んだ数だけOTUを除く。Leaphyでは平均して全OTU数の1/3が除かれる。除く数はランダムだが、除くOTUはランダムではない。現在の系統樹にフィットしないOTUから除いていく。"OTUごとの系統樹へのフィット"は、通常の２OTU間の配列距離と現在の系統樹（通常のbranch swappingで構築したもの）上での２OTU間の枝長を比べて、それらの乖離の大きさで判断する。乖離が大きいものほどフィットしていないと判断する。OTU除去後、残りの配列のみでbranch swappingによる樹形の改善を繰り返す。その後、除去した配列をstepwise additionにより改善した系統樹へ加えていく。

Whelan, S. (2007). New approaches to phylogenetic tree search and their application to large numbers of protein alignments. Syst. Biol. 56: 727–40.

Simulated annealing (SA)

Branch swappingにより樹形空間を探索する際、通常は最も尤度の高い提案樹形のみを受け入れる（＝貪欲法 greedy method）が、SAでは妥当な範囲であれば尤度が下がっても提案樹形を受け入れる。これにより、局所最適解にトラップされていても、尤度の谷の深さ次第ではそこから抜け出せるようになる。どのくらい尤度が下がってもよいかという指標は、探索を繰り返すごとに徐々に下がっていく。つまり、最初のうちはより多様な提案樹形を受け入れるが、提案→採用を繰り返すごとにその基準は厳しくなり、最後には尤度が高まる提案しか受け入れないようになる。受け入れ基準をどのように変化させるかは"cooling schedule"として設定できる。

Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P. (1983). Optimization by simulated annealing. Science 220: 671–80.

Metropolis-coupled Markov-chain Monte Carlo

ベイズ法による系統推定では、Markov-chain Monte Carlo (MCMC)法を使った樹形探索が行われる。これは、系統樹の樹形や枝長などのパラメーターに撹乱を与えながら、その事後分布を取得する方法であるが、樹形の変更にはおもにSPRやTBR操作が使われるので局所最適解に陥ってしまう可能性がつきまとう。

Metropolis-coupled MCMC (MCMCMC)法(Geyer, 1991)では、パラメーターの過激な撹乱を許容するマルコフ鎖（高温系列）を、穏当な撹乱のみを採択しやすいマルコフ鎖（低温系列）と並走させ、一定世代ごとにマルコフ鎖間でパラメーターを交換させる。ここでは、高温系列が局所最適解からの脱出を担い、低温系列がその後の微調整を担う。事後分布は低温系列のみから採取される。MCMCMC法はこのページ（外部リンク）で平易に説明してある。

Geyer, C.J. (1991). Markov Chain Monte Carlo Maximum Likelihood. In Computing Science and Statistics, Proceedings of the 23rd Symposium on the Interface (Interface Foundation of North America), pp. 156–163.

Combination of branch swapping algorithms

NNIで局所最適解に陥ったらSPRやTBRで抜け出し、またNNIでrefinementを行う。これの繰り返し。組み合わせるbranch swapping algorithmsの中で最も探索範囲が広いものでも抜け出せない場合はどうしようもない。

Genetic algorithms (GA)

個々の樹形を集団内の個体に見立てて、生物進化のアルゴリズムを樹形探索に適用する。個々の樹形の尤度が個体の適応度に相当し、尤度が高い樹形ほど子孫（= neighbor tree）を多く残せる。branch swappingによる樹形の変更が生物の突然変異にあたり、樹形間でのsubtreeの交換によって組み替えも表現できる。決めた世代の数だけ進化させ、最尤系統樹を得る。局所最適解にトラップされた個体（樹形）はそれ以上適応度（尤度）を上げることができないため、世代を追うごとに絶滅する確率が高まる。結果、局所最適解に陥らなかった系列の個体が最終世代まで残りやすい。