Felsenstein's tree-pruning algorithm: Difference between revisions

Revision as of 18:22, 23 January 2024

Latest revision as of 15:27, 4 October 2024

(2 intermediate revisions by 2 users not shown)

Line 5:

== Details ==

[[File:Tree_exemple.png|thumb|A simple phylogenetic tree exempleexample made from arbitrary data D]]

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

Line 11:

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 independantindependent''' of each other. This permits to compute the likelihood as a simple product of probabilities. Now you can divide the data <math>D</math> between several <math>D_s</math> for each nucleotide site <math>s</math> inside of <math>D</math>. The global likelihood of the tree will be the product of the likelihoods of each site:

[[File:Tree_partial_exemple.png|thumb|Same tree but made from D1, which consists in the first DNA sites from D]]

<math>

Line 17:

</math>

If I reuse the exempleexample above, <math>D_1</math> tree would be:

Line 42:

<math> w_k (X) = ( \sum_Y p_{X \rightarrow Y} \centerdot w_i (Y)) \centerdot ( \sum_Z p_{X \rightarrow Z} \centerdot w_j (Z)) </math>

where <math> Y </math> and <math> Z </math> are also DNA bases. <math> p_{ X\rightarrow Y} </math> is the transition probability from nucleotide <math>X</math> to nucleotide <math> Y </math> (idem for <math> p_{X \rightarrow Z} </math>). <math> w_i(Y) </math> is the partial likelihood of the daughter node <math>

i

</math>, evaluated on nucleotide <math> Y </math> (idem for <math>

Line 56:

== Algorithm ==

== Simple ExempleExample ==

==References==