樹形探索法
系統樹の作成は、モデル選択や枝の信頼性評価など数段階のステップを含むが、このページでは樹形(tree topology)を得る方法に絞ってまとめる。
Exhaustive search
全樹形探索。現代の一般的な計算機に頼る場合、OTU数が僅少な場合にのみ適用可能。例えば、50 OTUからなる系統樹には、2.75*10^76通りのrooted treeが存在する。この数は宇宙の全原子数に匹敵し、事実上計算不可能である(Whelan, 2007)。
Whelan, S. (2007). New approaches to phylogenetic tree search and their application to large numbers of protein alignments. Syst. Biol. 56: 727–40.
Branch-and-bound search
多分枝を含む大雑把な系統樹を比べて、最適解でないものはそれ以上細かな探索を行わず切り捨てる。最終的には大域的最適解が得られることが保証され、なおかつ全樹形探索よりも探索範囲を限定することができるが、それでもOTU数が多くなると現実的な時間内に計算できなくなってくる。最節約法で利用される。
Hendy, M.D. and Penny, D. (1982). Branch and bound algorithms to determine minimal evolutionary trees. Math. Biosci. 59: 277–290.
Heuristic search
発見的探索法。大域的最適解が得られる保証はない。最尤法の場合、通常はstepwise addition/star decomposition/distance matrix method等で初期系統樹を生成したのちに、branch swappingによって樹形空間を探索していく。
Heuristic search: Stepwise addition
まず、アラインメントに含まれる全OTUから３つをランダムに選び出し、（最尤法の場合は）最尤系統樹を構築する。無根系統樹の枝数は2 * (OTU数) - 3なので、この系統樹の枝数は３である。次に、残りのOTUから１つをランダムに選び出し、３つの枝にそれぞれ挿入した場合を比べ、最尤系統樹を選び出す。この時点で、OTU数は４、枝数は５である。さらに、残りのOTUから１つをランダムに選び出し、５つの枝にそれぞれ挿入した場合を比べ、最尤系統樹を選び出す。。。と続けることで、最終的にはすべてのOTUを含む最尤系統樹が得られる。この方法の問題点は、OTUを付加する順番に依存して探索範囲が変化するところであるが、少なくとも局所最適解であることが保証される。
Yang et al. (2006)の日本語訳から引用
Yang, Z., 藤博幸（翻訳）, 加藤和貴（翻訳）, and 大安裕美（翻訳） (2009). 分子系統学への統計的アプローチ -計算分子進化学-.
Ziheng, Y. (2006). Computational Molecular Evolution (Oxford University Press: Oxford, UK).
Lemey, P., Salemi, M., and Vandamme, A.-M. eds (2009). The Phylogenetic Handbook: A Practical Approach to Phylogenetic Analysis and Hypothesis Testing 2nd ed. (Cambridge University Press: Cambridge).
Heuristic search: Star decomposition
Stepwise additionとは逆に、すべてのOTUが１つのノードで結ばれた星状樹(star tree)を開始点とし、OTUを順次小さなグループに分割していく。
Yang et al. (2006)の日本語訳から引用
Heuristic search: Distance matrix method
OTUのすべてのペア組み合わせに対して任意の基準で距離行列を計算し、それを元に系統樹を構築する方法。通常、stepwise additionかstar decompositionのどちらかの手順で系統樹を得る。
Heuristic search: Distance matrix method: Least squares (LS)
最小二乗法。距離行列上の距離と、系統樹上の距離（OTU間の枝長の総和）の差が最小となるように系統樹を構築する方法。
Heuristic search: Distance matrix method: Neighbor joining (NJ)
近隣結合法。全OTUが１つのノードによって結ばれる星状樹(star tree)からスタートし、距離行列上で最も近い距離にあるOTUペアを結合する（近隣結合）。これを繰り返すことで、最終的にすべての枝が二分岐した系統樹が得られる。
変法として、枝長の推定の際に距離の推定値の分散と共分散を取り入れたBioNJ法がある(Gascuel, 1997)。進化速度が枝ごとに大きく異なる場合、NJ法よりも優れた結果を返す (Yang, 2006)。
WEIGHBOR法(Weighted neighbor-joining method)は、系統樹にOTUを加える際に近似的な尤度を評価する(Bruno et al., 2000)。
Saitou and Nei (1987)から引用
Saitou, N. and Nei, M. (1987). The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4: 406–425.
Gascuel, O. (1997). BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data. Mol. Biol. Evol. 14: 685–695.
Bruno, W.J., Socci, N.D., and Halpern, A.L. (2000). Weighted Neighbor Joining: A Likelihood-Based Approach to Distance-Based Phylogeny Reconstruction. Mol. Biol. Evol. 17: 189–197.
Heuristic search: Distance matrix method: Minimum evolution
最小進化法。枝長の総和が最小となるように距離行列から系統樹を構築する方法。
Desper, R. and Gascuel, O. (2002). Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. J. Comput. Biol. 9: 687–705.
Heuristic search: Distance matrix method: Unweighted pair group method using arithmetic average (UPGMA)
非加重結合法。分子進化速度が系統樹全体で一定であることを仮定する。距離行列上で最も近いOTUペアから順に系統樹上に加えていく。種以上の分類群を扱う場合、進化速度一定は成り立たないことが多いので使用は適切ではない (Yang, 2006)。
Sokal, R.R. and Sneath, P.H.A. (1963). Numerical Taxonomy (W.H. Freeman and Co.: San Francisco, CA).
Heuristic search: Quartet Puzzling
すべての組み合わせの４OTUに対して最尤系統樹を作る。OTUが４つの場合は全部で３通りの樹形があるので、その中の一つが最尤系統樹である。
複数の４OTU最尤系統樹を組み合わせていく。
intermediateな樹形すべてを考慮して多数決一致系統樹を作る。
この変法に、Important quartet puzzlingなどがある。
STRIMMER, K. and VON HAESELER, A. QUARTET PUZZLING : A QUARTET MAXIMUM-LIKELIHOOD METHOD FOR RECONSTRUCTING TREE TOPOLOGIES . Mol. Biol. Evol. 13: 964–969.
Vinh, L.S. and Von Haeseler, A. (2004). IQPNNI: moving fast through tree space and stopping in time. Mol. Biol. Evol. 21: 1565–71.
Heuristic search: Disk-covering method (DCM)
Quartet puzzlingのように複数の小さな系統樹を組み上げていく方法。データセットに含まれるOTUを、重複を許して少数のグループに分け、系統樹を構築する。このとき、構築方法は問わないが、NJ法などを使うことができる。次に、少数OTUの系統樹を組み合わせるが、このとき樹形の不一致があれば多分岐にする。その結果、全OTUから成る多分岐を含む系統樹が得られるが、これを最後に（最尤法なら）最も尤度が高くなるように再配置してすべての枝を二分岐にする。下の図は複数の少数OTU系統樹を１つに組み上げる手順を表す。
Huson et al. (1999)から引用
Huson, D.H., Nettles, S.M., and Warnow, T.J. (2004). Disk-Covering, a Fast-Converging Method for Phylogenetic Tree Reconstruction.
Heuristic search: Branch swapping
初期系統樹を与え、一定の手順（NNI, SPR, TBRがポピュラー)に従って樹形を変更してneighbor treesを得る。neighbor treesの中から（最尤法の場合は）最尤系統樹を選び出し、次の樹形変更の初期系統樹とする。樹形変更を何度も繰り返すことで探索範囲を広げる。通常、樹形変更を行うごとにすべてのneighborにおいて枝長を最適化した上で尤度を算出するが、枝長の最適化をせずとも尤度が高いneighborがあればそれを採用する、といった変法もある(Guindon et al., 2010)。neighbor treesの中に初期系統樹よりも尤度が高い樹形が現れなくなった時点で探索を終了する。探索空間があまりにも広い場合は、計算時間を制限してそこで強制終了させることもある。TBR > SPR > NNIの順で探索範囲が広い。
Lemey et al. (2009)から引用
Heuristic search: Branch swapping: Nearest neighbor interchange (NNI)
探索するneighbor treesの数はOTU数に比例する。
系統樹上の１つの枝は４つのsub treesの結合関係を表している。その組み合わせは、((A,B),(C,D))、((A,C),(B,D))、((A,D),(B,C))の３通りが存在し、NNI法では、系統樹上の任意の枝を選んでこの３つの樹形の（最尤法であれば）尤度を比較する。３つのうち１つは初期樹形に相当するので、実際には残り２つの樹形で新たに尤度を計算し、初期樹形と比べて尤度が最も高いものを選ぶ。NNI操作は、Robinson (1971)のcrossover操作と同一である (Robinson anf Foulds, 1981)。
Robinson, D.. (1971). Comparison of labeled trees with valency three. J. Comb. Theory, Ser. B 11: 105–119.
Robinson, D.F. and Foulds, L.R. (1981). Comparison of phylogenetic trees. Math. Biosci. 53: 131–147.
Heuristic search: Branch swapping: Subtree pruning and regrafting (SPR)
系統樹上の任意のsubtreeを切断し、その切断部位を元の系統樹のすべての枝に再接続を試み、（最尤法であれば）最も尤度が高い系統樹を選び出す。探索するneighbor treesの数はOTU数の二乗に比例する。
FASTDNAMLでは、subtreeを挿入する枝を元の位置から一定距離以内に限定することで、元の樹形からの大幅な変更を抑制し、計算時間を低減している (Olsen et al., 1994; Stewart et al., 2001)。
PHYML-SPRと呼ばれる変法では、minimum evolution principle (Desper and Gascuel, 2002)で生成したSPR neighborを評価し、有望でないものを探索対象から除外する。minimum evolution法は距離行列から系統樹を作成する方法であり、最尤法よりも高速にneighborを評価できる。PHYML 3.0では、minimum evolutionの代わりに最節約法が使われている(Guindon et al., 2010)。このステップで除外されなかった残りのneighborから通常の手順で最尤系統樹を選び、次のステップの初期系統樹とする。さらに、PHYML-SPRでは樹形変更によって変更が生じた枝のみを枝長最適化することで計算負荷を低減している (Hordijk and Gascuel, 2005)。
RAxMLにはLazy subtree rearrangement (LSR, Stamatakis et al., 2005)と呼ばれるSPRの変法が実装されている。LSRでは、FASTDNAMLでの実装のようにsubtreeの切断と挿入位置を一定距離以内に制限する（最大で25枝）。さらに、切断・挿入によって新たに生じた部分のみに対して枝長最適化を行っている。
MrBayesにはextending-SPRとparsimony-biased SPRという変法が実装されている。extending-SPRでは、subtreeの切断位置と再接続位置が遠いほど提案される確率が低くなる。parsimony-biased SPRは、提案樹形のparsimony score (その樹形における総置換数)に応じて提案される頻度が変化する。parsimony scoreを得る過程では、最節約系統樹を求める必要はないため高速に計算できる。
Olsen, G.J., Matsuda, H., Hagstrom, R., and Overbeek, R. (1994). fastDNAml: a tool for construction of phylogenetic trees of DNA sequences using maximum likelihood. Bioinformatics 10: 41–48.
Stewart, C.A., Hart, D., Berry, D.K., Olsen, G.J., Wernert, E.A., and Fischer, W. (2001). Parallel Implementation and Performance of FastDNAml - A Program for Maximum Likelihood Phylogenetic Inference.: 32.
Desper, R. and Gascuel, O. (2002). Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. J. Comput. Biol. 9: 687–705.
Hordijk, W. and Gascuel, O. (2005). Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood. Bioinformatics 21: 4338–47.
Guindon, S., Dufayard, J.-F., Lefort, V., Anisimova, M., Hordijk, W., and Gascuel, O. (2010). New algorithms and methods to estimate maximum-likelihood phylogenies: assessing the performance of PhyML 3.0. Syst. Biol. 59: 307–21.
Heuristic search: Branch swapping: Tree bisection and reconnection (TBR)
系統樹の任意のsubtreeを切断し、元の系統樹とsubtreeのすべての枝ペアの組み合わせで再接続を試み、（最尤法であれば）最も尤度が高い系統樹を選び出す。SPRではsubtreeの切断点が常に元の系統樹への再接続部位として使われるのに対し、TBRではsubtreeのすべての枝を再接続部位として試す。探索するneighbor treesの数はOTU数の三乗に比例する。１回のTBR操作は２回のSPR操作によって表すことができる。
MrBayesにはextending-TBRという変法が実装されている。この方法では、まず１つの枝を選び、接している２つのノードを選んだ枝の反対側にあるsubtreeのどこかに移動させる。図はRonquiest et al. (2005)から引用した。
Ronquist, F., Huelsenbeck, J.P., and van der Mark, P. (2005). MrBayes 3.1 Manual.
Heuristic search: Branch swapping: Subtree swap
無作為に２つの枝を選び、それらの位置を交換する方法。右図はHöhna and Drummond (2012)から引用した。
Drummond, A.J., Nicholls, G.K., Rodrigo, A.G., and Solomon, W. (2002). Estimating Mutation Parameters, Population History and Genealogy Simultaneously From Temporally Spaced Sequence Data. Genetics 161: 1307–1320.
Höhna, S. and Drummond, A.J. (2012). Guided tree topology proposals for Bayesian phylogenetic inference. Syst. Biol. 61: 1–11.
Heuristic search: Branch swapping: Edge contractions and refinements (ECR)
決められた個数だけ隣り合う枝をcollapseして多分岐とし、（最尤法であれば）最も尤度が高くなる解き方で再び二分岐に戻す。下の図は２つの枝を潰して再配置しているので、2-ECRとなる。NNIの変法であると言えるだろう。実際、1-ECRはNNIに相当する。詳細は追っていないが、おそらく、一度に探索するneighborの数はOTU数に比例する。
Ganepathy et al. (2004)から引用
Sankoff, D., Abel, Y., and Hein, J. (1994). A tree, a window, a hill; generalization of nearest-neighbor interchange in phylogenetic optimization. J. Classif. 11: 209–232.
Ganapathy, G., Ramachandran, V., and Warnow, T. (2004). On contract-and-refine transformations between phylogenetic trees.: 900–909.
Heuristic search: Branch swapping: Symmetric neighborhood alterations to phylogenies (SNAP)
NNIでは１つの枝を取り除いて新たな組み合わせを模索するのに対し、SNAPではcentering pointからの一定距離（radius）以内にあるすべての枝を取り除き、発生したsubtreesのすべての結合組み合わせを試す。枝とノードのどちらでもcentering pointとして指定できる。また、radiusはedgeの数もしくは枝長で指定する。当然、radiusが大きいほど探索範囲は広くなる。基本的にはNNIの変法なので、探索するneighbor treesの数はOTU数に比例し、指数関数的な増加はしない。
Whelan (2007)から引用
Whelan, S. (2007). New approaches to phylogenetic tree search and their application to large numbers of protein alignments. Syst. Biol. 56: 727–40.
Heuristic search: Branch swapping: Clock-constrained tree proposal operators
Branch swappingを分岐の深さで制限した変法は、Höhna et al. (2008)にまとめられている。
Hohna, S., Defoin-Platel, M., and Drummond, A.J. (2008). Clock-constrained tree proposal operators in Bayesian phylogenetic inference. In 2008 8th IEEE International Conference on BioInformatics and BioEngineering (IEEE), pp. 1–7.