On the variance of internode distance under the multispecies coalescent

Sébastien Roch

Abstract

We consider the problem of estimating species trees from unrooted gene tree topologies in the presence of incomplete lineage sorting, a common phenomenon that creates gene tree heterogeneity in multilocus datasets. One popular class of reconstruction methods in this setting is based on internode distances, i.e. the average graph distance between pairs of species across gene trees. While statistical consistency in the limit of large numbers of loci has been established in some cases, little is known about the sample complexity of such methods. Here we make progress on this question by deriving a lower bound on the worst-case variance of internode distance which depends linearly on the corresponding graph distance in the species tree. We also discuss some algorithmic implications.

Introduction

In evolutionary biology, reconstructing the "tree of life" is complicated by the fact that the evolutionary history of individual genes (gene trees) often differs from the overall history of the species (the species tree). This phenomenon, known as Incomplete Lineage Sorting (ILS), arises when lineages fail to coalesce within the time frame of a single ancestral species branch.

To address this, researchers employ "summary methods" that aggregate information from many gene trees to infer the species tree. A prominent class of these methods utilizes internode distance: the average number of edges (graph distance) between two species across a set of sampled gene trees. While methods like NJst and ASTRID are known to be statistically consistent—converging to the true tree as the number of genes approaches infinity—their sample complexity remains poorly understood. Specifically, it is unclear how many genes are required to achieve a reliable reconstruction as the number of species grows.

The Multispecies Coalescent (MSC) model. Gene lineages (black lines) evolve and coalesce within the constraints of the species tree branches (shaded regions).

Methods

This study provides a theoretical analysis of internode distance variance under the Multispecies Coalescent (MSC) model. The MSC is the standard probabilistic framework for modeling how gene lineages merge within a species tree.

To derive a lower bound on variance, the author constructs a "worst-case" species tree: a caterpillar tree characterized by a backbone of alternating branch lengths:

  • Short branches ($f$): These maximize local uncertainty by making coalescence less likely, thereby increasing variance in gene tree topologies.
  • Long branches ($g$): These serve as buffers, ensuring that lineages almost certainly coalesce before reaching the next section of the tree. This makes the variance contributions from different parts of the backbone approximately independent.

By treating the total distance as a sum of these nearly independent, high-variance blocks, the author applies the conditional variance formula to establish a lower bound on the total variance.

Key Results

The primary contribution of this work is Theorem 1, which establishes two formal lower bounds for the variance of the internode distance ($\hat{\delta}_{int}$) given $m$ genes:

  1. Path-dependent bound: $\text{Var}[\hat{\delta}_{int}(\ell, \ell')] \geq C \frac{d_g^{S_u}(\ell, \ell')}{m}$ The variance is at least proportional to the graph distance ($d_g$) between species $\ell$ and $\ell'$ in the species tree, divided by the number of genes ($m$).

  2. Worst-case bound: $\max \text{Var}[\hat{\delta}_{int}] \geq C \frac{n}{m}$ In a tree with $n$ species, the maximum variance scales linearly with $n/m$.

These results imply that to maintain a constant level of reconstruction accuracy, the number of genes $m$ must scale at least linearly with the number of species $n$. This requirement is more stringent than that of some other methods, such as quartet-based approaches (e.g., ASTRAL), which may only require the number of genes to scale logarithmically with $n$.

Discussion

The finding that variance accumulates linearly with graph distance highlights a potential vulnerability in distance-based reconstruction methods. While quartet methods focus on local relationships, distance methods aggregate noise over long evolutionary paths.

Several limitations of this analysis suggest avenues for future work:

  • Lower Bound Nature: As a lower bound, this result establishes a minimum variance; actual variance in practice could be significantly higher.
  • Correlation: The proof treats pairs of species in isolation, whereas distances between different pairs are highly correlated. These correlations might be exploitable by future algorithms to mitigate noise.
  • Estimation Error: The analysis assumes perfect knowledge of gene tree topologies. In practice, gene trees are estimated from sequence data, which introduces additional error and likely increases sample complexity requirements.

Finally, the author suggests that "fast-converging" distance methods—those prioritizing short distances or tree "depth"—might circumvent this linear scaling, offering a promising direction for algorithmic development.

Summary updated

Abstract

We consider the problem of estimating species trees from unrooted gene tree topologies in the presence of incomplete lineage sorting, a common phenomenon that creates gene tree heterogeneity in multilocus datasets. One popular class of reconstruction methods in this setting is based on internode distances, i.e. the average graph distance between pairs of species across gene trees. While statistical consistency in the limit of large numbers of loci has been established in some cases, little is known about the sample complexity of such methods. Here we make progress on this question by deriving a lower bound on the worst-case variance of internode distance which depends linearly on the corresponding graph distance in the species tree. We also discuss some algorithmic implications.
BibTeX
@misc{roch2018variance,
  author = {Sébastien Roch},
  title = {{On the variance of internode distance under the multispecies coalescent}},
  year = {2018},
  eprint = {1812.08357},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1812.08357},
}
Figure