TY - JOUR
T1 - A Two-Stage Pruning Algorithm for Likelihood Computation for a Population Tree
JF - Genetics
JO - Genetics
SP - 1095
LP - 1105
DO - 10.1534/genetics.107.085753
VL - 180
IS - 2
AU - RoyChoudhury, Arindam
AU - Felsenstein, Joseph
AU - Thompson, Elizabeth A.
Y1 - 2008/10/01
UR - http://www.genetics.org/content/180/2/1095.abstract
N2 - We have developed a pruning algorithm for likelihood estimation of a tree of populations. This algorithm enables us to compute the likelihood for large trees. Thus, it gives an efficient way of obtaining the maximum-likelihood estimate (MLE) for a given tree topology. Our method utilizes the differences accumulated by random genetic drift in allele count data from single-nucleotide polymorphisms (SNPs), ignoring the effect of mutation after divergence from the common ancestral population. The computation of the maximum-likelihood tree involves both maximizing likelihood over branch lengths of a given topology and comparing the maximum-likelihood across topologies. Here our focus is the maximization of likelihood over branch lengths of a given topology. The pruning algorithm computes arrays of probabilities at the root of the tree from the data at the tips of the tree; at the root, the arrays determine the likelihood. The arrays consist of probabilities related to the number of coalescences and allele counts for the partially coalesced lineages. Computing these probabilities requires an unusual two-stage algorithm. Our computation is exact and avoids time-consuming Monte Carlo methods. We can also correct for ascertainment bias.
ER -