Felsenstein's tree-pruning algorithm

File:Tree_exemple.png

The likelihood of a tree $T$ is, by definition, the probability of observing certain data $D$ ($D$ being a nucleotide sequence alignment for example i.e. a succession of $n$ DNA site $s$) given the tree. It is often written : $P(D|T)$.

Here is an example of an evolutionary tree on arbitrary sequence data $D$:

This is a key value and is often quite complicated to compute. To ease the computations, Felsenstein and his colleagues used several assumptions that are still widely used today. The main assumption is that mutations between DNA sites are independent of each other. This permits to compute the likelihood as a simple product of probabilities. Now you can divide the data $D$ between several $D\_s$ for each nucleotide site $s$ inside of $D$. The global likelihood of the tree will be the product of the likelihoods of each site:

File:Tree_partial_exemple.png

$$

P(D|T) = \prod_{s=1}^{n} {P(D_s|T)}

If I reuse the example above, $D\_1$ tree would be:

The second assumption concerns the models of DNA sequence evolution. The computation of the likelihood needs the nucleotide frequencies as well as the transition probabilities (when a mutation occurs, probability of going from a nucleotide to another). The simplest model is the Jukes-Cantor model, assuming equal nucleotide frequencies $\backslash left(\backslash pi\_A\; =\; \backslash pi\_G\; =\; \backslash pi\_C\; =\; \backslash pi\_T\; =\; \{1\backslash over4\}\backslash right)$ and equal transition probabilities from $X$ to $Y$ ($p\_\{A\; \backslash rightarrow\; T\}\; =\; p\_\{A\; \backslash rightarrow\; C\}\; =\; p\_\{A\; \backslash rightarrow\; G\}\; =\; \backslash frac\{1\}\{4\}\; (1\; -\; e^\{-\backslash mu\; l\})$ and $p\_\{A\; \backslash rightarrow\; A\}\; =\; e^\{-\backslash mu\; l\}\; +\; \backslash frac\{1\}\{4\}\; (1\; -\; e^\{-\backslash mu\; l\})$) and idem for the other bases. Here $\backslash mu$ is the global mutation rate of the model.

Felsenstein proposed to decomposed computations even more by using "partial likelihoods" in the computation of $$

P( D_s | T)

. Here is how it works.

Assume we are on a node $$

k

on the tree $$

T

. $$

k

has two daughter nodes $$

i

and $$

j

and, for each DNA base $X\; =\; \backslash \{\; A,\; T,\; C,\; G\; \backslash \}$ present on $$

k

, we can define a partial likelihood $w\_k\; (X)$ such as:

$w\_k\; (X)\; =\; (\; \backslash sum\_Y\; p\_\{X\; \backslash rightarrow\; Y\}\; \backslash centerdot\; w\_i\; (Y))\; \backslash centerdot\; (\; \backslash sum\_Z\; p\_\{X\; \backslash rightarrow\; Z\}\; \backslash centerdot\; w\_j\; (Z))$

where $Y$ and $Z$ are also DNA bases. $p\_\{\; X\backslash rightarrow\; Y\}$ is the transition probability from nucleotide $X$ to nucleotide $Y$ (idem for $p\_\{X\; \backslash rightarrow\; Z\}$). $w\_i(Y)$ is the partial likelihood of the daughter node $$

i

, evaluated on nucleotide $Y$ (idem for $$

w_j(Z)

).

Using this formula, one has to start from the tips of the tree $T$, then move towards the root and compute the partial likelihoods of each necessary node on the way (4 partial likelihoods per node). Having finished at the root of the tree, the likelihood of the tree (for this particular site) is then the sum of the partial likelihoods of the root times the appropriated nucleotide frequency.

$P(D\_s|T)\; =\; \backslash sum\_X\; p\_X\; \backslash centerdot\; w\_r\; (X)$

After doing so for every site $s$, one can finally obtain the likelihood of the global evolutionary tree by multiplying each "sublikelihood".

{{reflist}}

{{genetics-stub}}

{{statistics-stub}}

Category:Statistical genetics