The Bayesian "Star Paradox" Persists for Long Finite Sequences

Mike Steel, F. A. Matsen

TL;DR

This paper mathematically proves that the "star paradox" in phylogenetic inference—where an unresolved "star" tree can still strongly support a specific resolved tree—persists even with infinitely long DNA sequences. This resolves a debate by showing that the tendency for misleading strong support doesn't vanish with more data, challenging the intuition that more data always leads to more accurate inference.

What Problem Does This Paper Address?

In phylogenetics, researchers reconstruct evolutionary relationships between species using DNA sequences. A "star tree" represents a scenario where multiple species diverged simultaneously from a common ancestor, meaning their evolutionary relationships are unresolved. However, analyses sometimes show strong statistical support for a specific, resolved tree structure (e.g., species A diverged from B, and then both diverged from C) even when the data was actually generated by a star tree. This phenomenon is known as the "star paradox."

A key question has been whether this paradox disappears as we analyze longer and longer DNA sequences. Some argued that with infinite data, all possible resolutions of a star tree would receive equal support, effectively eliminating the paradox. This paper directly addresses this by mathematically investigating the behavior of Bayesian phylogenetic inference with very long sequences, specifically for the case of a three-taxon star tree.

Methods

The authors tackle this problem through rigorous mathematical proof. They focus on a simplified model of DNA evolution (a 2-state symmetric Markov process) and a three-taxon star tree. The core of their approach involves:

  • Bayesian Inference Framework: They analyze posterior probabilities of different tree topologies given the sequence data.
  • Mathematical Modeling: They derive equations for the probabilities of different DNA site patterns under a star tree.
  • Asymptotic Analysis: They investigate the behavior of these probabilities as the sequence length ($n$) approaches infinity.
  • Probability Theory and Statistics: They employ concepts like multinomial and multinormal distributions, expectation, and conditional probabilities to analyze the behavior of posterior probabilities.
  • A Novel Lemma: They introduce and prove a specific lemma (Lemma 2.2) that provides a tool to bound the ratio of expected values of random variables under certain conditions, which is crucial for demonstrating that a specific posterior probability remains significantly high.

The proof is structured to be general, applying to a "reasonable" class of priors on branch lengths, meaning it's not overly dependent on a specific prior choice.

Datasets

Not discussed in the paper. The paper focuses on theoretical mathematical proofs and simulations, not empirical data analysis.

Key Insights and Ideas

  • The Paradox Persists: The most significant finding is the mathematical proof that the star paradox does not disappear with increasing sequence length. Even with infinitely long sequences, a specific resolved tree can still be strongly supported by data generated from a star tree.
  • "Limit of a Function" vs. "Function of a Limit": The paper highlights a crucial distinction in statistics: the limit of a function of random variables (like site pattern frequencies) as $n \to \infty$ is not always the same as the function of the limit of those random variables. This is why infinite-length sequence simulations might be misleading.
  • Generic Result: The proof is designed to be general, relying on minimal assumptions about the prior distributions of branch lengths. This suggests the phenomenon is robust and not an artifact of specific prior choices.
  • Challenging Intuition: The result challenges the intuitive notion that "more data always means better inference." In this specific scenario, more data doesn't necessarily resolve the ambiguity inherent in a star tree in a way that eliminates misleading strong support for a particular resolution.

Key Results

The paper's main result is Theorem 2.1, which states that for sequences of length $n$ generated by a star tree with positive branch lengths, and for any "reasonable" prior on the three possible resolved trees and their branch lengths, the probability that a specific resolved tree $T_i$ has a posterior probability greater than $1 - \epsilon$ (for any small $\epsilon > 0$) does not converge to zero as $n$ tends to infinity. In simpler terms, there's always a non-vanishing chance that a resolved tree will be strongly supported, no matter how long the sequence gets.

Limitations and Future Work

  • Simplified Model: The mathematical proof uses a simplified 2-state symmetric Markov model for DNA evolution. While the authors suggest the argument extends to more general models, this simplification is a limitation for direct application to real-world, complex evolutionary processes.
  • Three-Taxon Case: The proof is specifically for a three-taxon star tree. Extending this to scenarios with more taxa would be a natural next step.
  • Explicit Calculation of Limits: The authors identify an "interesting open question" to explicitly calculate the limit of the posterior density $f(P_1, P_2, P_3)$ described in prior work (Yang and Rannala 2005). This would provide a more detailed understanding of how the paradox manifests with infinite data.
  • Implications for Bayesian Phylogenetics: While the paper demonstrates the existence of the paradox, it notes that it's not the purpose of this work to delve into the broader implications for Bayesian phylogenetic analysis. Further research could explore these implications more deeply.

Summary updated

Abstract

The "star paradox" in phylogenetics is the tendency for a particular resolved tree to be sometimes strongly supported even when the data is generated by an unresolved ("star") tree. There have been contrary claims as to whether this phenomenon persists when very long sequences are considered. This note settles one aspect of this debate by proving mathematically that the chance that a resolved tree could be strongly supported stays above some strictly positive number, even as the length of the sequences becomes very large.
BibTeX
@inproceedings{steel2007bayesian,
  author = {Mike Steel and F. A. Matsen},
  title = {{The Bayesian "Star Paradox" Persists for Long Finite Sequences}},
  booktitle = {Molecular},
  year = {2007},
  doi = {10.1093/molbev/msm028},
}
Figure