Felsenstein's tree-pruning algorithm
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In statistical genetics, Felsenstein's tree-pruning algorithm (or Felsenstein's tree-peeling algorithm), attributed to Joseph Felsenstein, is an algorithm for efficiently computing the likelihood of an evolutionary tree from nucleic acid sequence data. The algorithm is often used as a subroutine in a search for a maximum likelihood estimate for an evolutionary tree. Further, it can be used in a hypothesis test for whether evolutionary rates are constant (by using likelihood ratio tests). It can also be used to provide error estimates for the parameters describing an evolutionary tree.
In statistical genetics, Felsenstein's tree-pruning algorithm (or Felsenstein's tree-peeling algorithm), attributed to Joseph Felsenstein, is an algorithm for efficiently computing the likelihood of an evolutionary tree from nucleic acid sequence data. The algorithm is often used as a subroutine in a search for a maximum likelihood estimate for an evolutionary tree. Further, it can be used in a hypothesis test for whether evolutionary rates are constant (by using likelihood ratio tests). It can also be used to provide error estimates for the parameters describing an evolutionary tree. 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 \left(\pi_A = \pi_G = \pi_C = \pi_T = {1\over4}\right) and equal transition probabilities from X to Y ( p_{A \rightarrow T} = p_{A \rightarrow C} = p_{A \rightarrow G} = \frac{1}{4} (1 - e^{-\mu l}) and p_{A \rightarrow A} = e^{-\mu l} + \frac{1}{4} (1 - e^{-\mu l}) ) and idem for the other bases. Here \mu is the global mutation rate of the model. Felsenstein proposed to decompose 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 = \{ A, T, C, G \} present on k , we can define a partial likelihood w_k (X) such as: w_k (X) = ( \sum_Y p_{X \rightarrow Y} \centerdot w_i (Y)) \centerdot ( \sum_Z p_{X \rightarrow Z} \centerdot w_j (Z)) where Y and Z are also DNA bases. p_{ X\rightarrow Y} is the transition probability from nucleotide X to nucleotide Y (idem for p_{X \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) = \sum_X p_X \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".
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1343540708 under CC BY-SA 4.0; modifications have been made.