Phylogenetics (evolutionary biology)
The standard method of phylogenetics, determining the evolutionary tree for a group of species, is with Bayesian evidence integrals. These are usually computed by Monte Carlo sampling, but the integrals the samplers approximate can often be done exactly. Exact evidence extends the reach of phylogenetic tree reconstruction and settles subtle questions about which species branched when.
Trees and the marginal likelihood
A phylogenetic tree records which species descend from which common ancestors, and today it is inferred largely from molecular data: DNA accumulates substitutions over time, so species whose sequences differ little parted recently. Line up the same gene from several species, one row per species and one column per position. A column in which human and chimpanzee share one letter while gorilla and orangutan share another supports grouping human with chimpanzee.
Four species can be joined into an unrooted tree (one that records the branching but not where the deepest ancestor sits) in exactly three ways, and five species in fifteen. At these sizes every candidate can be written down and scored. Bayesian phylogenetics, introduced in the late 1990s and now standard, scores a tree topologyThe branching pattern of a tree: which species are joined to which, regardless of how long the branches are. $T$ by its posterior probability, which for equally weighted trees is proportional to the marginal likelihood, or evidence:

The three possible trees for four species, drawn as a physicist draws scattering channels: the four species stay fixed at the corners (human, chimpanzee, gorilla, orangutan) and only the internal line is re-routed. Pairing the left column against the right is the $s$-channel (12|34), pairing the rows is the $t$-channel (13|24), and pairing across the diagonals crosses the legs, the $u$-channel (14|23). Choosing among the three is the whole problem for a quartet.
$$ Z(T\mid u) \;=\; \int p(u\mid T,t)\,\pi(t\mid T)\,\mathrm{d}t . $$Here $u$ is the alignment, summarized by how many columns show each pattern of agreement; $t$ is the list of branch lengths, in expected substitutions per site; $p(u\mid T,t)$ is the probability of the data given the tree and its branch lengths, computed by Felsenstein’s pruning algorithm of 1981; and $\pi(t\mid T)$ is a priorA probability distribution stating which branch lengths are considered plausible before the data are seen. on the branch lengths. The ratio of two trees’ marginal likelihoods is a Bayes factorThe ratio of the marginal likelihoods of two hypotheses; here, of two trees or two substitution models. Comparisons on this page use its natural logarithm, in “log units” (nats). A log Bayes factor of 3 is the conventional threshold for strong evidence., and its natural logarithm gives the “log units” in which every comparison below is stated.
Why the integral has always been estimated
The integral has one dimension per branch (five for a four-species tree, or quartet) and has been regarded as analytically intractable for all but trivial cases. In 1996 Rannala and Yang obtained posterior probabilities for four hominoid species by direct numerical integration, an approach limited to about five taxa, as the tips of a tree are called. For larger trees the integral is estimated from the output of a Markov chain Monte CarloA simulation that takes a long random walk through the possible branch lengths, visiting each region in proportion to its probability. sampler that wanders through branch-length space. Thermodynamic integration (brought to phylogenetics in 2006) and stepping-stone samplingAn estimator (Xie and colleagues, 2011) that climbs from the prior to the posterior through a ladder of intermediate distributions, each proportional to the prior times the likelihood raised to a power β between 0 and 1, and multiplies together the estimated ratios between neighboring rungs (“stones”). Thermodynamic integration instead integrates the average log-likelihood along the same ladder by a quadrature rule. (2011) are the estimators now in standard use, the latter built into MrBayes, RevBayes and BEAST; LoRaD (2023) is a recent addition. In 2020 Fourment and colleagues compared nineteen such methods, under the title “19 dubious ways to compute the marginal likelihood of a phylogenetic tree topology.”
Earlier comparisons of marginal-likelihood estimators shared one limitation: the reference value was the analytic answer of a textbook model that is not a tree, or another estimator, or a very long run of the same sampler. None of them used an exactly known marginal likelihood of a tree on real sequence data, so each program’s run-to-run scatter was known but not its distance from the true value.
The integral is a fraction
The simplest model of DNA change is the Jukes–Cantor model of 1969: every letter mutates to each of the other three at the same rate. Along a branch of length $t$, the probabilities that a site keeps its letter, or ends with one particular different letter, are
$$ P_{\text{same}}(x) \;=\; \tfrac14 + \tfrac34\,x, \qquad P_{\text{different}}(x) \;=\; \tfrac14 - \tfrac14\,x, \qquad x \;=\; e^{-4t/3}. $$The variable $x$ runs from 1 for a branch of zero length to 0 for an infinitely long one, and both probabilities are linear in it. Pruning multiplies one such factor per branch and sums over the unknown letters at the two internal nodes. The probability of any column is therefore a polynomial in the five branch variables $x_1,\dots,x_5$, of degree at most one in each, with integer coefficients divided by 256. Because the model treats the four letters alike, the 256 possible columns collapse into fifteen pattern classesThe set partitions of four species by shared letter: xxxx (all agree), xxyy (species 1 and 2 agree against 3 and 4), xxxy (only species 4 differs), and so on down to xyzw (all four differ). An alignment enters the computation only through the fifteen counts of columns in each class.. MrBayes and RevBayes offer an independent exponential prior on each branch length; at rate $4/3$ (mean 0.75 substitutions per site) the change of variables makes it uniform in $x$. The evidence becomes the integral of a polynomial over the unit cube, taken one term at a time:
$$ Z(T\mid u) \;=\; \int_{[0,1]^5} \prod_{k=1}^{15} p_k(x)^{u_k}\,\mathrm{d}x_1\cdots\mathrm{d}x_5 \;=\; \frac{1}{256^{N}} \sum_{a} c_a \prod_{e=1}^{5} \frac{1}{a_e+1} . $$On the left, $p_k$ are the fifteen class polynomials and $u_k$ the observed counts for an alignment of $N$ columns. On the right, the product has been expanded into monomials $x_1^{a_1}\cdots x_5^{a_5}$ with integer coefficients $c_a$, and each power $x^{a}$ replaced by its integral over the unit interval, $1/(a+1)$. A finite sum of fractions is a fraction. The proof of that statement is itself the algorithm, traced in the figure below. The same argument covers any exponential prior of rational rate, Kimura’s 1980 two-parameter model and, by a different route, any time-reversible model, once the extra rate parameters and base frequencies are fixed at rational values.

From alignment to fraction, on a twenty-column worked example. Top: a four-species alignment, each column tinted by its pattern class, that is, by which species share a letter. Middle: the tree being scored, with one variable $x_e$ on each of its five branches, beside the count of columns in each class; only six of the fifteen classes occur in this alignment. Pruning turns each class into a polynomial that is linear in every $x_e$, and the likelihood is the product of those polynomials raised to their counts. Under the uniform prior on each $x_e$, every term of the expanded product integrates to a product of reciprocals of whole numbers. Bottom: the result, a 49-digit integer over an 87-digit integer. No step involves a random number or a rounding. (Redrawn from Figure 1 of the first paper.)
975764089122942807922559239182988593336005689311686648380848617182632879055070822400000
The evidence of the tree 12|34 for the twenty-column example, exactly: a 49-digit integer over an 87-digit one, about $8.6\times10^{-39}$, so that $\log Z = -87.64924335\ldots$ to as many digits as wanted. A sampler reports only an estimate of this logarithm with a statistical error.
Expanding the product of class polynomials is expensive, however: up to $(N+1)^5$ monomials, with coefficients hundreds of digits long. Most columns in a real alignment are constant or support the tree being scored, and those factor out cheaply; only the $m$ mixedA column is mixed, for the tree being scored, if it is neither constant nor of the one class that supports that tree (species 1 and 2 sharing one letter and 3 and 4 another, for the tree pairing 1 with 2). Constant and supporting columns factor out of the computation cheaply; mixed columns do not. columns need the full expansion, so the cost scales as $N(m+1)^5$. The same construction works for five and even six species, with seven and nine branch variables in place of five, but the cost then grows as the seventh and ninth power of the mixed-column count, so each added species is far more expensive. Every step runs in modular arithmeticArithmetic that keeps only the remainder after division by a fixed prime, so every intermediate number stays small however large the true integers grow., a technique taken from the exact evaluation of Feynman integrals (von Manteuffel and Schabinger, 2015). The computation is repeated modulo several primes just below $2^{31}$, and the Chinese remainder theorem reassembles the exact integer with no floating-pointOrdinary computer arithmetic, which keeps about sixteen significant digits of every number and rounds away the rest. operation anywhere. In the variables $x_e$ the evidence has the form of a Feynman integral in parametric representation, which algebraic statisticians call a GKZ hypergeometric integral.
The reference alignment on real data is the mitochondrial transfer-RNATransfer RNAs are short adapter molecules, roughly 70 to 90 nucleotides long (mitochondrial ones run shorter), that carry amino acids to the ribosome during protein synthesis. Their genes are among the shortest there are, short enough for the exact computation. gene tRNA-Gln in mouse, rat, chicken and the frog Xenopus: 68 columns, 25 of them mixed for the mouse–rat tree (32 and 33 for the other two trees). Each of its three evidences is a ratio of integers of roughly 190 and 300 digits, and the tree pairing mouse with rat, the accepted one, wins by 14.54 and 15.56 log units. On 72 cores, all three took about three times the elapsed time of a single-core MrBayes run; two classic 900-column alignments, with hundreds of mixed columns, remain out of reach. Alignment size is one limit and the substitution model is another: once the rate is allowed to vary from column to column, the evidence is no longer a finite sum of fractions. With gamma-distributed rate variation across sites, three species and a single constant column at gamma shape 1 already give $(10-6G)/64$, with $G = 0.5963\ldots$ the Euler–Gompertz constant, a number computable to any precision but presumably irrational.
An exact tie among the great apes
A second transfer-RNA gene, tRNA-Phe, in human, chimpanzee, gorilla and orangutan, produces an exact tie between two trees. The alignment has 69 columns, 59 constant and 10 carrying a change private to one species, none grouping two apes against the other two. Computed separately, the evidences of the human–chimpanzee tree and of the chimpanzee–gorilla tree came out as the same 217-digit integer over the same 287-digit integer. The tie follows from a symmetry that played no part in the computation: swapping the labels “human” and “gorilla” leaves every pattern count unchanged and carries one tree into the other. The third tree, pairing human with gorilla, maps to itself under the swap and is tied to neither. It has the largest evidence of the three, by 0.0013 log units, although no column supports it; human and gorilla are the two sequences with the fewest private changes, and the small margin in their favor traces to an interaction between the likelihood and the branch-length prior. Stepping-stone runs on this alignment scatter by 0.017 to 0.067 log units, and no finite sample can show a difference to be exactly zero.
Adding the gibbon gives fifteen trees, and all fifteen have been computed exactly. The human–gorilla swap still preserves the counts: the three trees that join human with gorilla map to themselves, and the other twelve fall into six exactly tied pairs. The top value, $\log Z = -189.6451$, is shared by the accepted hominoid tree, with human and chimpanzee paired and orangutan and gibbon paired, and its mirror with chimpanzee and gorilla paired. The human–gorilla resolution that nominally won at four species now ranks third, 0.5625 log units behind. The two columns where human and gorilla differ have become informative, and both count against joining them.

The three ways to resolve human, chimpanzee and gorilla, scored exactly without and with the gibbon. Each symbol is one tree’s exact log evidence relative to the best tree (Jukes–Cantor model, exponential branch-length priors of mean 0.75, equal prior weight on trees). Left, the four-ape tRNA-Phe quartet: the tree pairing human with gorilla leads by 0.0013 log units, and the other two are equal as ratios of integers, as the human–gorilla label swap requires. Right, all fifteen five-ape trees on the same gene, on a far coarser scale: the accepted tree and its mirror under the swap tie at the top, and the human–gorilla tree falls 0.5625 log units behind. Of the twelve remaining trees (gray), ten form five more exactly tied pairs; the other two also join human with gorilla and tie with nothing. (Exact values of Tables 2 and 4 of the first paper, redrawn after its Figure 5.)
Testing the estimators against the answer
The exact values then serve to measure the accuracy of the estimators, with the sampler settings fixed beforehand. On the tRNA-Gln quartet the exact evidence of the accepted tree is a ratio of integers of about 190 and 300 digits whose logarithm is $\log Z = -261.4031$; the stepping-stone estimates of MrBayes and RevBayes and the LoRaD estimate all land within a few hundredths of a log unit of it, and repeated MrBayes runs differ among themselves by 0.02 to 0.07. The MrBayes means, however, sit below the exact values on every tree. Longer chains and more stones remove part of the gap; a residual of −0.016 log units does not move and is common to the three trees. It disappears when one of MrBayes’s three default branch-length proposals, the node slider, is switched off: from version 3.2.4 onward that move’s proposal ratio contains one extra factor of the ratio of new to old tree length, so that MrBayes, run without data and with that move alone, samples trees 1.4 to 3 times longer than the prior mean. The offset cancels in these Bayes factors and is far below any threshold used to interpret one, but nothing MrBayes reports reveals it; a much longer MrBayes run, used as the reference, would make the other two programs look biased instead. RevBayes errs with both signs, and its errors shrink toward zero as the budget grows; LoRaD agrees with the exact values within its chain-to-chain spread.
A second test separates two estimators that use the same samples. On a three-species, eight-column alignment every ratio along a four-stone stepping-stone path can be computed without sampling. Stepping-stone sampling reproduces the exact $\log Z = -29.4932$ within Monte Carlo error at every budget. Thermodynamic integration over the same four intervals comes out low by 0.0095 log units, 39 standard errors at the largest budget: the trapezoidal rule misses the curvature between so few stones, and sampling longer at each stone does not help.
Beyond one gene: a tortoise and the malaria mosquitoes
Two applications go beyond these test genes, one of them to the extinct San Cristóbal giant tortoise of the Galápagos. From one stretch of mitochondrial DNA (a locus) of about 700 nucleotides, Jensen and colleagues (2022) placed it as sister to two other Chelonoidis species with posterior probability 1.0. Exact Bayes factors put that placement to a test under a design fixed in advance: the test statistic was the sum of twelve exact log Bayes factors for the published grouping, over two quartets and six segments of the locus, and confirmation required a sum of at least 3.0 with both quartet sums of the same sign. The observed sum is 0.90, and the two quartets disagree in sign, −3.61 and +4.51. Post-mortem DNA damage does not explain the shortfall: 150 replicates with such damage introduced all score below −43. The published placement rests on a molecular-clockAn analysis that assumes substitutions accumulate at a roughly steady rate, so that sequence differences can be converted into times. analysis of 93 distinct sequences, and this test does not say it is wrong; the conclusion is only that this locus, analyzed this way, does not confirm it.
In the Anopheles gambiae complex of African malaria mosquitoes, Fontaine and colleagues (2015) found one species grouping differently on the autosomes (the non-sex chromosomes) and on the X chromosome. Rerunning their sliding-window scan in floating-point arithmetic, 81,113 windows on three quartets each, taking no position on gene flowThe transfer of genetic material from one species or population into another through interbreeding., recovers the reversal. Exact values were then computed for the 5,375 window–quartet pairs within two size limits set in advance. Of these, 2,997 are exact ties, which floating point can break only by rounding error. Among the 2,378 with a unique exact winner, floating point picks the same tree in all but four, and those four are separated by at most 0.016 log units.
JaCK & Jill: the method as software
The computation is available as a Python package under the name JaCK & Jill: JaCK for the exact Jukes–Cantor and Kimura computations, Jill for the interval and sampling routines. Given an alignment, a topology and a model, one call returns a marginal likelihood as one of four kinds of answer and reports which. An exact value is the fraction itself, under Jukes–Cantor for alignments about the length of a transfer RNA and under Kimura’s model for shorter ones. A proven interval brackets the value under the richer HKY85 and GTR+Γ models at fitted parameters, given enough computing time (a short run may prove only an upper bound). An estimate, by quasi-Monte Carlo importance samplingImportance sampling draws branch lengths from a fitted stand-in distribution and reweights each draw; quasi-Monte Carlo spreads the draws evenly instead of at random., works at any length; on small Jukes–Cantor quartets (up to about 32 columns) it also carries an indicative error figure, 0.014 log units, derived from deviations measured against exact values. A proof of a tie is a permutation of the taxa that preserves the pattern counts and carries one topology into the other. Every answer comes with a machine-readable record that an independent routine rechecks against the alignment.
The exact values are then the reference for a benchmark on nine problems: the three trees each of the tRNA-Gln and four-ape tRNA-Phe quartets, and the three leading five-ape trees (figure below). At 2.5 million likelihood evaluations the phyloexact estimate misses by 0.0001 log units on average. On the three tRNA-Gln trees MrBayes stepping-stone sampling is off by about 0.024 and RevBayes by about 0.017, compared with 0.0003 for phyloexact; LoRaD, run on the quartets, is off by about 0.005. Per single-thread run at that budget they take roughly 7 to 13 seconds against 31 for uncompiled phyloexact. The like-for-like comparisons favor phyloexact more strongly: at its default budget it runs in about four seconds per problem (about one second with the optional compiled kernel) with a mean error of 0.0006 log units. At equal run time, about 7 seconds, its error is 20 to 44 times below LoRaD’s and 67 to 213 times below the two stepping-stone programs’. The best of the nineteen methods from the 2020 comparison, all run in the program physher, reaches 0.0026 log units at twenty times the budget, 26 times the phyloexact error. For scale, against the conventional Bayes-factor threshold of 3 log units the stepping-stone and LoRaD errors are negligible, while thousandths of a log unit can matter where two values nearly tie and where one-signed errors accumulate over many loci.

Error against the exact answer versus computing budget, on the nine transfer-RNA problems with exactly known marginal likelihoods. Each mark is one method’s mean distance from the exact log marginal likelihood, plotted against the number of likelihood evaluations a single run spends; both axes are logarithmic. Crosses are the nineteen estimators of the 2020 comparison, run in physher at their default budgets and labeled by family; open symbols are MrBayes and RevBayes stepping-stone sampling and LoRaD; the diamonds are the phyloexact estimate at its default budget and at the benchmark budget of 2.5 million evaluations. The upper dashed line is the conventional strong-evidence threshold of 3 log units and the lower one marks a thousandth of a log unit. At a matched budget the package’s estimate sits one to two orders of magnitude below the programs in everyday use. Because the reference values are exact, every height on the plot is a measured error, independent of what each program reports about its own uncertainty. (Values of Table 3 of the JaCK & Jill paper and Table S18 of its supplement, redrawn after its Figure 3.)
The package scores a given topology and does not search over trees. For five taxa, under the Jukes–Cantor model, it ranks the fifteen trees by a certified maximum-likelihood comparison, abstaining when rivals cannot be separated, and on short alignment windows returns certified upper and lower bounds on each tree’s evidence; the fifteen exact great-ape values above ship with the package as verified reference values. Beyond five taxa it offers the Jukes–Cantor estimate and tie proofs for up to 32 taxa. It runs 38 validation tests with one command and is free software under the MIT license.
The papers
- Exact Bayesian evidence for phylogenetic trees (PDF) — Matthew D. Schwartz, Scott V. Edwards and Paul O. Lewis. A preliminary version of the paper.
- JaCK & Jill: exact marginal likelihoods for small phylogenetic trees (PDF) — the same authors. A preliminary version of the paper.
Supplementary material
- Supplementary material (PDF) — the phyloexact manual: installation and a first session, every call with its options, returned objects and refusals, the models available for each kind of answer, the error statement of the estimate, cost planning, the full benchmark tables, and the format of the machine-readable records.
- JaCK & Jill tool page — this site’s documentation of the phyloexact package, which computes the exact evidence and Bayes factors of four-species trees under the Jukes–Cantor model, the transfer-RNA examples above among them.
References
| T. H. Jukes and C. R. Cantor, Evolution of protein molecules, in Mammalian Protein Metabolism (H. N. Munro, ed.), vol. III, Academic Press (1969) 21 | the one-rate substitution model under which the evidence is a fraction |
| M. Kimura, A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences, J. Mol. Evol. 16 (1980) 111 | the two-parameter model, also covered with its rate ratio fixed at a rational value |
| J. Felsenstein, Evolutionary trees from DNA sequences: a maximum likelihood approach, J. Mol. Evol. 17 (1981) 368 | the pruning algorithm that computes the probability of an alignment on a tree |
| I. M. Gel’fand, M. M. Kapranov and A. V. Zelevinsky, Generalized Euler integrals and A-hypergeometric functions, Adv. Math. 84 (1990) 255 | the GKZ (A-)hypergeometric integrals, the class to which the evidence belongs in the branch variables $x_e$ |
| B. Rannala and Z. Yang, Probability distribution of molecular evolutionary trees: a new method of phylogenetic inference, J. Mol. Evol. 43 (1996) 304 | posterior probabilities for four hominoid species by direct numerical integration |
| N. Lartillot and H. Philippe, Computing Bayes factors using thermodynamic integration, Syst. Biol. 55 (2006) 195 | thermodynamic integration brought to phylogenetics |
| W. Xie, P. O. Lewis, Y. Fan, L. Kuo and M.-H. Chen, Improving marginal likelihood estimation for Bayesian phylogenetic model selection, Syst. Biol. 60 (2011) 150 | stepping-stone sampling, the estimator now built into MrBayes, RevBayes and BEAST |
| F. Ronquist et al., MrBayes 3.2: efficient Bayesian phylogenetic inference and model choice across a large model space, Syst. Biol. 61 (2012) 539 | MrBayes; its stepping-stone runs show the small offset traced to the node slider |
| A. von Manteuffel and R. M. Schabinger, A novel approach to integration by parts reduction, Phys. Lett. B 744 (2015) 101 | modular arithmetic for Feynman integrals, the technique adopted for the exact evaluation |
| S. Höhna, M. J. Landis, T. A. Heath, B. Boussau, N. Lartillot, B. R. Moore, J. P. Huelsenbeck and F. Ronquist, RevBayes: Bayesian phylogenetic inference using graphical models and an interactive model-specification language, Syst. Biol. 65 (2016) 726 | RevBayes; its stepping-stone estimates err with both signs and converge on the exact values as the budget grows |
| M. Fourment, A. F. Magee, C. Whidden, A. Bilge, F. A. Matsen IV and V. N. Minin, 19 dubious ways to compute the marginal likelihood of a phylogenetic tree topology, Syst. Biol. 69 (2020) 209 | the comparison of nineteen estimators, rerun in the second paper against exact values |
| Y.-B. Wang, A. Milkey, A. Li, M.-H. Chen, L. Kuo and P. O. Lewis, LoRaD: marginal likelihood estimation with haste (but no waste), Syst. Biol. 72 (2023) 639 | the LoRaD estimator, which agrees with the exact values within its run-to-run spread |
| E. L. Jensen et al., A new lineage of Galapagos giant tortoises identified from museum samples, Heredity 128 (2022) 261 | the San Cristóbal tortoise placement that the first paper tests on one locus |
| M. C. Fontaine et al., Extensive introgression in a malaria vector species complex revealed by phylogenomics, Science 347 (2015) 1258524 | the malaria-mosquito genome scan rebuilt and checked against exact values |