Felsenstein のツリー剪定アルゴリズム

統計遺伝学において、ジョセフ・フェルゼンシュタインに帰属するフェルゼンシュタインのツリー剪定アルゴリズム（またはフェルゼンシュタインのツリー剥離アルゴリズム）は、核酸配列データから進化樹の尤度を効率的に計算するアルゴリズムである。 ^{[1] [2]}

このアルゴリズムは、進化樹木の最大尤度推定値を求めるサブルーチンとしてよく使用されます。さらに、進化速度が一定であるかどうかの仮説検定にも使用できます (尤度比検定を使用)。また、進化樹木を記述するパラメータの誤差推定値を提供するためにも使用できます。

ツリーの尤度は、定義により、ツリーが与えられた場合に特定のデータ(たとえばヌクレオチド配列のアラインメント、つまりDNA部位の連続)が観測される確率です。次のように記述されることが多いです。 ${\displaystyle T}$${\displaystyle D}$${\displaystyle D}$${\displaystyle n}$${\displaystyle s}$${\displaystyle P(D|T)}$

以下は任意のシーケンスデータ上の進化ツリーの例です。 ${\displaystyle D}$

これは重要な値であり、計算が非常に複雑になることがよくあります。計算を容易にするために、フェルゼンシュタインと彼の同僚は、今日でも広く使用されているいくつかの仮定を使用しました。主な仮定は、 DNA サイト間の突然変異は互いに独立しているということです。これにより、尤度を単純な確率の積として計算できます。これで、内の各ヌクレオチド サイトについて、データを複数の に分割できます。ツリーの全体的な尤度は、各サイトの尤度の積になります。 ${\displaystyle D}$${\displaystyle D_{s}}$${\displaystyle s}$${\displaystyle D}$

${\displaystyle P(D|T)=\prod _{s=1}^{n}{P(D_{s}|T)}}$

上記の例を再利用すると、ツリーは次のようになります。 ${\displaystyle D_{1}}$

2番目の仮定は、DNA 配列の進化のモデルに関するものです。尤度の計算には、ヌクレオチド頻度と遷移確率 (突然変異が発生したときに、あるヌクレオチドから別のヌクレオチドに遷移する確率) が必要です。最も単純なモデルはJukes-Cantor モデルで、からへのヌクレオチド頻度と遷移確率が等しい(および)と仮定し、他の塩基についても同様と仮定します。これがモデルの 全体的な突然変異率です。${\displaystyle \left(\pi _{A}=\pi _{G}=\pi _{C}=\pi _{T}={1 \over 4}\right)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle p_{A\rightarrow T}=p_{A\rightarrow C}=p_{A\rightarrow G}={\frac {1}{4}}(1-e^{-\mu l})}$${\displaystyle p_{A\rightarrow A}=e^{-\mu l}+{\frac {1}{4}}(1-e^{-\mu l})}$${\displaystyle \mu}$

Felsenstein は、 の計算に「部分尤度」を使用して、計算をさらに分解することを提案しました。その仕組みは次のとおりです。 ${\displaystyle P(D_{s}|T)}$

ツリー のノードにいると仮定します。には 2 つの娘ノードとがあり、に存在する各 DNA 塩基に対して、次のような部分尤度を定義できます。 ${\displaystyle k}$${\displaystyle T}$${\displaystyle k}$${\displaystyle i}$${\displaystyle j}$${\displaystyle X=\{A,T,C,G\}}$${\displaystyle k}$${\displaystyle w_{k}(X)}$

${\displaystyle w_{k}(X)=(\sum _{Y}p_{X\rightarrow Y}\centerdot w_{i}(Y))\centerdot (\sum _{Z}p_{X\rightarrow Z }\centerdot w_{j}(Z))}$

ここで、 およびも DNA 塩基です。はヌクレオチドからヌクレオチドへの遷移確率です( についても同様)。はヌクレオチドで評価された娘ノードの部分尤度です( についても同様)。 ${\displaystyle Y}$${\displaystyle Z}$${\displaystyle p_{X\rightarrow Y}}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle p_{X\rightarrow Z}}$${\displaystyle w_{i}(Y)}$${\displaystyle i}$${\displaystyle Y}$${\displaystyle w_{j}(Z)}$

この式を使用すると、ツリーの先端から始めて、ルートに向かって移動し、途中の必要な各ノードの部分尤度を計算する必要があります (ノードごとに 4 つの部分尤度)。ツリーのルートで終了すると、ツリーの尤度 (この特定のサイトの場合) は、ルートの部分尤度の合計に適切なヌクレオチド頻度を掛けたものになります。 ${\displaystyle T}$

${\displaystyle P(D_{s}|T)=\sum _{X}p_{X}\centerdot w_{r}(X)}$

すべてのサイトに対してこれを実行した後、各「サブ尤度」を乗算することで、最終的にグローバル進化ツリーの尤度を得ることができます。 ${\displaystyle s}$