On estimating the effective sample size of phylogenetic trees in an autocorrelated chain

arXiv:2603.03521 · q-bio.PE · Submitted 2026-03-03 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Genomics Radio. Generated commentary on the latest computational biology and genomics papers.

Ines: Today's paper: "On estimating the effective sample size of phylogenetic trees in an autocorrelated chain".

Marcus: Estimating the effective sample size (ESS) of phylogenetic trees in an autocorrelated chain is fundamental in Bayesian phylogenetic inference to properly account for autocorrelation in MCMC samplesThe gist A key…

Ines: First, who's behind it and why it matters.

Title and authors: Ines: We're now looking at the title and authors of this paper, "On estimating the effective sample size of phylogenetic trees in an autocorrelated chain," and what that actually means for our work.

Marcus: The title immediately tells you that they are focusing on the effective sample size or ESS for phylogenetic trees when they are stuck in an autocorrelated chain, which is a key problem we face when running MCMC simulations.

Yuki: So, it's about getting a handle on how many independent samples you actually get from those chains because the dependence between consecutive samples lowers that count.

Ines: The authors are Klawitter and his team at Simon Fraser University, but they also have collaborators across other institutions like Australian National University and the University of Canterbury.

Marcus: That's a pretty diverse group, which is typical in this kind of research where you need expertise spanning computational methods and evolutionary biology to tackle something so complex.

Yuki: Having people from different backgrounds helps bring in different perspectives on how to model the inherent challenges of tree space versus continuous parameter spaces.

Ines: It highlights that the difficulty isn't just in calculating an ESS, but in finding a way for estimation methods to work within the specific geometry of treespace.

Marcus: Exactly, and they are trying to move beyond existing tools that only work for continuous variables and apply them here despite the non-Euclidean nature of tree space.

Yuki: That speaks to the wider problem in species evolution where we have these complex, high-dimensional spaces that defy simple geometric intuition.

Ines: So, essentially, they are trying to make sense of how to get a reliable count of independent samples when your samples are inherently linked by the way you're exploring tree space.

Marcus: And this paper suggests there are specific ways to do that using tools tailored for trees, moving away from just treating them like continuous data points.

Yuki: It’s an important piece because it shows a path toward more robust statistical inference when we analyze phylogenetic relationships across different taxa.

The paper's summary: Ines: Now, let's look at the main summary of this paper, "On estimating the effective sample size of phylogenetic trees in an autocorrelated chain," and what they claim their approach is.

Marcus: They summarize it by saying that while standard methods for continuous parameters are known, the discrete and high-dimensional nature of treespace creates substantial challenges for ESS estimation.

Yuki: So they’re setting up the problem clearly: the space isn't smooth like a line or a plane, which means existing ESS estimators don't apply directly.

Ines: They then propose two main avenues: one is extending tree-to-trace mappings using Conditional Clade Distributions, or CCDs.

Marcus: The paper suggests that CCDs allow for sampling a tree from the distribution and computing a probability of observing a specific tree within that distribution, which helps estimate the posterior distribution better.

Yuki: That sounds like they are using these distributions to make non-trivial instances of tree space more tractable for statistical analysis.

Ines: They also introduce a new probabilistic estimator based on clade frequencies observed across multiple independent MCMC chains as an alternative approach.

Marcus: This second method operates independently of distance metrics, autocorrelation time, and tuning parameters by directly estimating ESS from the observed counts of clades between those chains.

Yuki: That's interesting because it bypasses the need for complex geometric mappings entirely, focusing instead on how often certain evolutionary events occur in the sampled trees.

Ines: The paper then compares several specific estimators, like logP and mapRF against new ones such as fr´echetIPSE and cladeInd.

Marcus: They note that the initial positive sequence estimator of Tracer behaved most robustly for both small and large autocorrelation times, which is a good sign for general applicability.

Yuki: It’s valuable because it shows that even with these new methods, we still need to test how well they hold up across different scenarios of chain behavior.

Ines: So the summary is essentially: they are proposing two new ways—one using tree-to-trace mappings via CCDs and another based on clade frequency differences—to estimate ESS more effectively for trees.

The paper's improvements: Marcus: The paper outlines several specific improvements they suggest, particularly focusing on how to get better estimates from the estimators they test.

Ines: One major suggestion is leveraging Conditional Clade Distributions to map trees to numerical sequences using log probabilities, or logP.

Marcus: That means treating a tree as a sequence of numbers derived from its probability under the CCD, which should allow them to use existing ESS estimators for continuous variables more directly.

Yuki: If that works well, it suggests we can get better estimates for the posterior distribution of non-trivial trees than before.

Ines: They also suggest using mapRF by mapping distances to a set of reference trees from the sample and deriving ESS estimates from those traces, which is a distance-based approach.

Marcus: And they mention expRF, which looks at expected RF distances with respect to the CCD, which is another way of incorporating that distribution information.

Yuki: Those methods are conceptually different from each other, and comparing them allows us to see what kind of structural information—like distance or probability—is most helpful for estimating ESS in this context.

Ines: They also highlight the practical recommendation to use cladeInd by Fabreti and H¨ohna or pseudoMedianRF, which they call pseudoESS, because those have proven reliable and efficient.

Marcus: So the improvements boil down to choosing methods that are specifically designed for trees, like cladeInd or pseudoESS, over general-purpose estimators when you're dealing with autocorrelated chains.

Yuki: That gives us a concrete direction for how researchers should approach this problem in their own analyses of phylogenetic data.

Conclusion: Ines: To wrap up the paper, we're looking at the conclusion of "On estimating the effective sample size of phylogenetic trees in an autocorrelated chain," and what they ultimately conclude.

Marcus: They confirm that their new trace-based methods, when mapped using CCD log probabilities or distances to a CCD map, perform competitively with pseudoMedianRF.

Yuki: But they do acknowledge that these newer methods might introduce higher variance compared to the established ones.

Ines: The paper concludes by strongly recommending cladeInd by Fabreti and H¨ohna or pseudoMedianRF implemented as pseudoESS as the most reliable and efficient ESS estimation tools for tree topologies.

Marcus: The final thought is that robust ESS estimation for phylogenetic trees remains a fundamental challenge, but these methods offer a viable way to tackle it using trace-based techniques.

Yuki: And they also point out that being able to compute these estimates during the MCMC run could really help build automated convergence assessment frameworks, giving us real-time diagnostics.

Ines: So, this paper is a solid contribution by showing how to handle autocorrelation in tree space using novel mapping techniques and suggesting specific tools for practical use.

Marcus: We're done with this paper on estimating the effective sample size of phylogenetic trees in an autocorrelated chain, and we're ready to look at what else is happening in the field.

University of Auckland · Simon Fraser University · Research School of Biology, Australian National University

q-bio.PE

Submitted: 2026-03-03

Updated: 2026-10-09

Code: https://github.com/rbouckaert/asm

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 80/100

The gist: Estimating the effective sample size (ESS) of phylogenetic trees in an autocorrelated chain is fundamental in Bayesian phylogenetic inference to properly account for autocorrelation in MCMC

Key concepts

Effective Sample Size (ESS): ESS measures how many truly independent samples are needed to achieve the same statistical precision as correlated MCMC samples. It quantifies the quality of posterior estimates by accounting for autocorrelation in sequential sampling, which is crucial for accurate phylogenetic inference.
Autocorrelation Time (ACT): The ACT is a metric that defines how many MCMC iterations are required before the samples become effectively independent. A high ACT indicates strong autocorrelation, meaning the chain explores the parameter space slowly and requires more samples to achieve reliable estimates.
Conditional Clade Distributions (CCDs): CCDs are a new approach used to model tree space by allowing researchers to sample trees from a distribution D and calculate the probability of observing a specific tree T within that distribution. This technique helps overcome the limitations of existing methods designed for continuous parameters in discrete tree space.

Terminology

Accuracy — 1× in this paper · explained in 1 episode
Robustness — 1× in this paper · explained in 5 episodes

Summary

Estimating the effective sample size (ESS) of phylogenetic trees in an autocorrelated chain is fundamental in Bayesian phylogenetic inference to properly account for autocorrelation in MCMC samplesThe gist

Introduction and Challenges

A key challenge of MCMC is autocorrelation, which reduces the effective sample size (ESS) and lowers the precision of posterior estimatesThis dependence is quantified by the autocorrelation time (ACT), which measures the average number of iterations needed to obtain effectively independent samples<ref:2603.03521#pg3> The ESS quantifies how many independent samples would provide the same statistical precision as the autocorrelated MCMC samples<ref:2603.03521#pg3> Understanding the ESS is crucial for properly accounting for autocorrelation in downstream analyses and assessing the quality of posterior estimates<ref:2603.03521#pg3> The fundamental difficulty stems from the discrete, high-dimensional nature of treespace, which lacks the metric properties of Euclidean spaces and therefore cannot accommodate existing ESS estimation methods designed for continuous parameters<ref:2603.03521#pg5>.

Methodological Approaches

The paper presents two distinct methodological approaches for estimating tree ESSFirst, we extend the class of tree-to-trace mappings by leveraging Conditional Clade Distributions (CCD) [4, 23, 33]. Second, we propose a probabilistic estimator based on observed clade frequencies across multiple independent MCMC chains<ref:2603.03521#pg5>. The CCD allows for sampling a tree from D and computing the probability Pr(T) of a tree T in DThis allows it to provide a better estimate of the posterior distribution for non-trivial instances<ref:2603.03521#pg5>.

Tree ESS Estimators

Several estimators are compared, including logP, pseudoMedianRF, mapRF, expRF, and cladeInd<ref:2603.03521#pg7> The paper notes that the initial positive sequence estimator of Tracer behaved most robust for small and large ACT<ref:2603.03521#pg8>. Other methods include fr´echetIPSE, which adapts the initial positive sequence estimator (IPSE) to trees by estimating covariance and correlations via Fr´echet means and variances using squared RF distances<ref:2603.03521#pg8>. The paper recommends the use of cladeInd by Fabreti and H¨ohna [16] or pseudoMedianRF (implemented as pseudoESS) by Lanfear et al. [32]<ref:2603.03521pg8, Our practical recommendation for tree-based ESS estimation is to use cladeInd by Fabreti and H¨ohna [16] or pseudoMedianRF (implemented as pseudoESS) by Lanfear et al. [32]>These methods provide reliable and efficient ESS estimation for tree topologies<ref:2603.03521#pg9>.

Evaluation Framework

The evaluation framework combines simulated chains with known ESS bounds and robustness testing on real datasetsFor our simulated chains, we aim to establish ground truth by constructing chains with known, controllable ESS values and to ensure samples reflect realistic posterior distributions<ref:2603.03521#pg5>. Robustness is assessed by partitioning chains into k equally-sized fragments and summing the resulting estimatesThis approach has previously been used in the context of convergence assessment [3]<ref:2603.03521#pg9>.

Key Findings on Performance

The results show that all estimators except EDCF lie close to the diagonal, which represents a lower bound on the ESSAn MRE of zero indicates that an estimator matches the expected lower bound on average, while a positive MRE signals overestimation and a negative MRE indicates underestimation<ref:2603.03521#pg19>. The results indicate that datasets 2, 3, and 7 exhibit well-behaved additivity across all estimatorsThis suggests that these estimators are internally consistent with respect to additivity<ref:2603.03521#pg9>.

Conclusion

Our new trace-based methods, which map trees to numerical sequences via CCD log probabilities (logP), distances to the CCD MAP tree (mapRF), or expected RF distances with respect to the CCD (expRF), perform competitively with pseudoMedianRF, albeit with higher variance<ref:2603.03521#pg9>. Overall, our practical recommendation for tree-based ESS estimation is to use cladeInd by Fabreti and H¨ohna [16] or pseudoMedianRF (implemented as pseudoESS) by Lanfear et al. [32]<ref:2603.03521#pg9>. The paper highlights that effective sample size estimation for phylogenetic trees is a fundamentally challenging problemMethods that can be computed during MCMC runs further enable integration into automated convergence assessment frameworks, such as the ASM package [3], providing real-time diagnostics for practitioners<ref:2603.03521#pg10>. The paper concludes that robust ESS estimation for tree topologies remains fundamental to ensuring the validity of posterior inferenceThe gist

Availability

Our trace-based tree ESS estimates are available to use via the TreeStat2 package and TracerThe gist The code for the EDCF methods, fr´echetIPSE, and approximateESS are available in their own repository<ref:2603.03521#pg60>. The algorithm to compute the expected RF distance of a tree to a CCD is available in the CCD package/repository<ref:2603.03521#pg60>. The paper provides additional results on the autocorrelation signatures in Section A, on estimator accuracy in Section B, on their stability in Section C, and on their robustness in Section D as well as on the modality analysis (Section E) and trace plots (Section F)<ref:2603.03521#pg60>. The gist

References

The paper cites numerous works, including those by Lanfear et al. [32] and Magee et al. [35]The gist The paper also references works on MCMC diagnostics like Berling et al. [3]<ref:2603.03521#pg8>. The gist The paper includes references for software packages such as BEAST 2 and scikit-learnThe gist</ref:2603.

Improvements for AI systems

Immediate improvement in tree ESS estimation by introducing Conditional Clade Distributions (CCDs) to map trees to a tractable space, as this allows it [the CCD] to provide a better estimate of the posterior distribution for non-trivial instances. This enables the estimation of log probability and expected RF distance traces, offering distinct conceptual advantages over distance-based mappings.
Development of a novel probabilistic estimator based on clade frequencies between independent chains, termed Expected Difference of Clade Frequencies (EDCF), which operates independently of distance metrics, autocorrelation time, and tuning parameters. This estimator is proposed as a method to directly estimate the ESS from observed clade frequencies, offering an alternative to existing approaches.
Refinement of the evaluation framework by using simulated MCMC chains with known bounds on the ESS and applying controlled perturbations to simulate realistic autocorrelation patterns in RNNI treespace, thereby improving the accuracy assessment of existing estimators against ground truth.
Implementation of a robust stability test that assesses estimator performance under chain fragmentation, noting that poor mixing and multimodality can substantially affect this stability, which provides a diagnostic tool for identifying convergence issues in tree MCMC samples.
Creation of an online computation capability where cladeInd is noted as an estimator that can be computed online during the MCMC run, enabling its inclusion in automated convergence testing frameworks like the ASM package for real-time diagnostics.

Abstract

Estimating the effective sample size (ESS) is fundamental in Bayesian phylogenetic inference to account for autocorrelation in MCMC samples. While methods for continuous parameters are well established, the discrete and high-dimensional nature of treespace poses substantial challenges. In this paper, we introduce a new approach based on Conditional Clade Distributions (CCDs) to emulate MCMC chains with known ESS bounds. We compare existing tree ESS estimators with novel approaches that utilize CCDs as tractable tree distributions, as well as a new probabilistic estimator based on differences in clade frequencies between independent chains. Using our emulated chains from both simulated and real datasets, we assess estimators for their ability to recover the true ESS (accuracy), their insensitivity to the removal of autocorrelated samples from the chain (stability), and their tolerance to combining multiple chains together (robustness). We further examine how multimodality and poor inter-mode chain mixing can compromise the reliability of tree ESS estimates. These findings indicate that our new CCD-based estimators perform comparably to existing approaches with respect to accuracy, stability, and robustness. In contrast, the probabilistic estimator and two previously recommended methods incur prohibitive computational costs for long chains. Together, these results establish a new framework for evaluating tree ESS estimators using CCD-based emulated MCMC chains and demonstrate their performance and current limitations in practical phylogenetic analyses. The expanded suite of tree ESS estimators is available in the user-friendly TreeStat2 software package for BEAST 2.

Sources

Bayesian Credible Sets for Phylogenetic Tree Topologies with Applications to Coverage Analysis and Cross-Model Comparison