title: A two-stage pruning algorithm for likelihood computation for a population tree.
abstract: 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.
authors.affiliation: Department of Organismic and Evolutionary Biology, Harvard University, Cambridge, Massachusetts 02138, USA. aroy@fas.harvard.edu
authors.forename: Arindam
authors.initials: A
authors.lastname: RoyChoudhury
authors.forename: Joseph
authors.initials: J
authors.lastname: Felsenstein
authors.forename: Elizabeth A
authors.initials: EA
authors.lastname: Thompson
mesh_terms: D000465:Algorithms; D019143:Evolution, Molecular; D005828:Genetics, Population / Q000706:statistics & numerical data; D016013:Likelihood Functions; D020641:Polymorphism, Single Nucleotide
references.citation: Genetics. 1931 Mar;16(2):97-159
references.pmid: 17246615
references.citation: Am J Hum Genet. 1973 Sep;25(5):471-92
references.pmid: 4741844
references.citation: Evolution. 1998 Jun;52(3):669-677
references.pmid: 28565245
references.citation: Evolution. 2000 Feb;54(1):44-50
references.pmid: 10937182
references.citation: Am J Hum Genet. 1967 May;19(3 Pt 1):233-57
references.pmid: 6026583
references.citation: Genetics. 1985 Jun;110(2):325-44
references.pmid: 4007484
references.citation: Nucleic Acids Res. 2003 Jan 1;31(1):124-7
references.pmid: 12519964
references.citation: Genome Res. 2005 Nov;15(11):1496-502
references.pmid: 16251459
references.citation: J Mol Evol. 1981;17(6):368-76
references.pmid: 7288891
references.citation: Hum Hered. 1971;21(6):523-42
references.pmid: 5149961
references.citation: Clin Genet. 1972;3(6):501-4
references.pmid: 4650869