An Improved Bipartition Cover Bound for the Multispecies Coalescent Model

This paper presents improved, topology-free upper bounds on the number of loci required to achieve a bipartition cover under the multispecies coalescent model, offering tighter and more biologically realistic estimates than previous work while providing new theoretical insights into coalescence asymptotics.

The Gist

Imagine you are trying to reconstruct a family tree of a group of species (like lions, tigers, and leopards) based on their DNA. But here's the catch: DNA doesn't always tell a single, consistent story. Sometimes, a lion's DNA looks more like a tiger's than a leopard's, even though lions and leopards are closer relatives. This happens because of a biological phenomenon called Incomplete Lineage Sorting—think of it as a game of "telephone" where the genetic message gets scrambled as species diverge.

To solve this, scientists use a method called ASTRAL. Instead of looking at one gene, they look at thousands of genes (loci) and try to find the "majority vote" to build the true species tree.

However, ASTRAL has a safety net: it only works perfectly if the collection of gene trees contains every single branch (bipartition) of the true species tree. If even one branch is missing from the gene data, the method might get lost.

The big question is: How many genes do we need to collect to be sure we have every single branch?

This paper is about answering that question more accurately than ever before.

The Problem with the Old Rules

Previously, scientists had a formula to guess how many genes were needed. But this old formula was like a very cautious parent who assumes the worst possible scenario every time. It assumed that:

1. Every branch in the family tree was the shortest, most difficult one to find.
2. The family tree was shaped in the most confusing way possible.

Because of this, the old formula often said, "You need 100,000 genes!" when in reality, you might only need 1,000. It was so conservative that it made the method seem useless for many real-world studies where collecting that many genes is impossible.

The New Approach: Finding the "Worst-Case" Scenarios

The author of this paper, Zachary McNulty, decided to stop guessing and start analyzing the actual "worst-case" scenarios where finding branches is hardest. He identified two specific shapes of family trees that cause the most trouble:

1. The "Caterpillar" Tree: Imagine a family tree that looks like a long, wiggly caterpillar. One branch splits off, then another, then another, in a long line. In this shape, finding the deep branches is hard because there are so many of them.
2. The "Balanced" Tree: Imagine a perfectly symmetrical tree, like a pyramid or a balanced mobile. Every split divides the group exactly in half. This is tricky because the genetic lineages (the DNA strands) get spread out so evenly that they take a very long time to "merge" (coalesce) back together.

The paper shows that these two shapes are the true "boss battles" of evolutionary biology. By mathematically modeling exactly how genes behave in these specific, difficult shapes, the author created a new, sharper formula.

The Analogy: The Missing Puzzle Pieces

Think of the species tree as a giant jigsaw puzzle.

• The Old Formula assumed that every single piece of the puzzle was hidden in a dark, locked box, and you had to buy a million boxes to be sure you found them all.
• The New Formula realizes that while some pieces are in dark boxes, others are sitting right on the table. It calculates exactly how many boxes you need to open based on the average difficulty of the puzzle, rather than assuming the absolute worst case for every single piece.

The Results: A Massive Improvement

The new formula is a game-changer:

• It's Smarter: It accounts for the fact that in a "Balanced" tree, genes merge slowly, but in a "Caterpillar" tree, they merge quickly in some places and slowly in others.
• It's Practical: For many real-world scenarios, the new formula says you might need 10 to 100 times fewer genes than the old formula predicted. This means scientists can use existing datasets that were previously thought to be "too small" to be reliable.
• It's Theoretically Sound: The paper doesn't just guess; it uses advanced probability math (specifically something called "Kingman's Coalescent") to prove that these new numbers are the best possible estimates without knowing the exact shape of the tree beforehand.

The Bottom Line

This paper is like upgrading from a sledgehammer to a scalpel. The old method was safe but clumsy, often demanding more data than necessary. The new method is precise, telling scientists exactly how much data they need to feel confident in their evolutionary family trees, even when the data is messy or the family tree is weirdly shaped.

In short: We can now build better evolutionary trees with less data, saving time and money for researchers everywhere.

Technical Summary

1. Problem Statement

The paper addresses the problem of determining the number of gene loci ($n$) required to ensure that a collection of gene trees forms a bipartition cover of the underlying species tree with a prescribed probability ($q$).

• Context: In phylogenetics, summary methods like ASTRAL rely on the assumption that the true species tree's topology is contained within the set of bipartitions (splits) observed in the input gene trees. If this "bipartition cover" condition is met, ASTRAL provides strong finite-sample guarantees. If not, no guarantees exist.
• Challenge: The species tree topology is unknown during inference. Therefore, researchers need topology-free bounds (bounds that depend only on the number of species $k$ and the minimum branch length $T_{min}$, not the specific shape of the tree) to estimate the necessary sample size.
• Limitation of Existing Work: The previous state-of-the-art bound by Uricchio et al. [2016] is often overly conservative, predicting required locus counts that exceed biologically realistic limits (e.g., $>10^5$) for moderate numbers of species or short branch lengths.

2. Methodology

The author derives new, tighter topology-free upper bounds by analyzing the Multispecies Coalescent (MSC) model and identifying "worst-case" tree topologies that maximize the difficulty of recovering bipartitions.

Key Theoretical Tools

• Kingman's Coalescent: The probability $g_{i,j}(T)$ that $i$ lineages coalesce into $j$ lineages in time $T$ is the fundamental building block.
• Stochastic Dominance: The paper utilizes first-order ($X \ge_{st} Y$) and second-order ($X \ge_{sst} Y$) stochastic dominance to bound the number of lineages entering a specific edge in a species tree.
• Extremal Tree Topologies: The analysis identifies two opposing extremes:
  1. Caterpillar Trees: Maximize the number of descendants for internal edges (combinatorial bottleneck).
  2. Balanced Trees: Maximize the number of surviving lineages due to even dispersion of lineages, delaying coalescence (coalescent bottleneck).

Progressive Improvements

The paper develops a hierarchy of bounds, each improving upon the previous by refining the estimation of the "worst-case" scenario:

1. Refining Descendant Counts (Caterpillar Bound):

   • Original approach: Assumed the worst-case for every edge was having $k-2$ descendants.
   • Improvement: Recognized that edges near the root have fewer descendants. By summing the probabilities over all possible descendant counts $\ell$ (from 2 to $k-2$) rather than taking the maximum, the bound is significantly tightened. This assumes the Caterpillar tree is the worst case for the sum of probabilities.

2. Accounting for Deeper Coalescence (One-Step Bound):

   • Original approach: Assumed no coalescence occurs below the edge of interest before reaching it.
   • Improvement: Modeled the number of lineages entering an edge $e$ as a random variable $X_e$. By using Lemma 2.6, the author shows that the number of lineages is stochastically maximized when the subtree below $e$ is split as evenly as possible (balanced split). This replaces the deterministic count $k-2$ with a stochastic expectation involving a sum of coalescent processes.

3. Recursive Worst-Case (Balanced Bound):

   • Improvement: Extends the "balanced split" logic recursively down the entire tree.
   • Result: The Balanced Tree is proven to be the stochastic worst-case for the number of surviving lineages (Lemma 2.8). The bound is computed recursively: the number of lineages entering a balanced tree of size $\ell$ is the sum of lineages from two balanced subtrees of size $\approx \ell/2$, followed by one step of coalescence.
   • Formula: The new bound $M_b(k, T_{min})$ involves a recursive calculation of $w_\ell = P(W_\ell = 1)$, where $W_\ell$ represents the number of lineages surviving in a balanced tree of size $\ell$.

3. Key Contributions

• Tighter Topology-Free Bounds: The paper provides a new bound ($M_b$) that strictly improves upon the Uricchio et al. [2016] bound ($M_o$) and the intermediate "Caterpillar" ($M_c$) and "One-Step" ($M_s$) bounds.
• Identification of Extremal Topologies: It rigorously proves that while Caterpillar trees maximize the sum of descendant counts, Balanced trees are the true stochastic worst-case for the number of lineages surviving coalescence under the MSC.
• Asymptotic Analysis:
  • For fixed $T_{min}$ and large $k$, the original bound scales as $O(\log k)$.
  • The new balanced bound improves the constant factor significantly. In the regime of small $T_{min}$, the improvement factor is asymptotically $O(T_{min}^{-1})$.
  • Specifically, the ratio of the old bound to the new bound approaches $\frac{\pi^2}{2 T_{min}}$ as $T_{min} \to 0$.
• Dynamic Computation: The recursive nature of the balanced bound allows for efficient dynamic programming computation, making it practical for empirical use.

4. Results

• Simulation Performance:
  • The new bounds remain below biologically realistic thresholds (typically $10^3$ to $10^5$ loci) across a much broader range of $k$ and $T_{min}$ compared to the original bound.
  • The Balanced Bound ($M_b$) improves upon the original bound by several orders of magnitude in challenging regimes (large $k$, small $T_{min}$).
  • The Caterpillar Bound ($M_c$) offers only a small constant factor improvement, confirming that the "balanced" nature of the tree is the dominant factor in the difficulty of bipartition recovery.
• Overestimation Analysis:
  • The bounds are still conservative (overestimate the required $n$), particularly for Balanced trees.
  • However, for "average" trees (Yule model), the overestimation is significantly lower than the original bound, though still non-negligible.
  • The results suggest that while topology-free bounds are useful, incorporating partial topological information might be necessary for further tightening.

5. Significance

• Practical Utility: The improved bounds make the theoretical guarantees of summary methods like ASTRAL more applicable to real-world datasets. Researchers can now be more confident that their dataset size is sufficient to recover the species tree topology without needing impossibly large numbers of loci.
• Theoretical Insight: The work deepens the understanding of the Multispecies Coalescent model, specifically clarifying the distinct roles of tree shape (balanced vs. caterpillar) in the probability of lineage survival and bipartition recovery.
• Methodological Framework: The use of stochastic dominance and recursive worst-case analysis provides a robust framework for deriving bounds in other phylogenetic inference problems where topology is unknown.

In summary, McNulty's paper transforms the bipartition cover problem from a highly conservative, often impractical theoretical limit into a more precise, computable, and biologically relevant tool for phylogenomic study design.