📊 statistics

Consensus Tree Estimation with False Discovery Control via Partially Ordered Sets

This paper introduces a novel consensus tree estimation method that frames the problem as structured feature selection using partial orders to control the false discovery rate, accommodate diverse tree structures, and provide model-free guarantees, as demonstrated in a study on the origins of complex life.

Original authors: Maria Alejandra Valdez Cabrera, Amy D Willis, Armeen Taeb

Published 2026-08-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Maria Alejandra Valdez Cabrera, Amy D Willis, Armeen Taeb

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Life on Earth is often visualized as a vast, branching family tree, where every species is a leaf connected to others by a shared history. In fields ranging from biology to linguistics, scientists use these trees to map how things are related, whether tracing the evolution of ancient genes or the spread of a virus through a population. However, when researchers study these histories, they rarely find a single, perfect tree. Instead, they collect hundreds or thousands of different trees, each built from a different piece of evidence, like a gene or a language sample. These trees often disagree with one another, showing different connections or missing different species entirely. The challenge has long been how to summarize this messy collection into one clear picture without losing the truth or inventing false connections.

A team of statisticians and biologists at the University of Washington has developed a new way to solve this problem. They treat the task of finding a single "consensus" tree not as a simple averaging process, but as a careful selection game where every branch and every leaf is a candidate feature. Their goal is to build a summary tree that includes only the connections strongly supported by the data, while rigorously controlling the risk of including a connection that is actually wrong. They created a mathematical framework that allows them to count exactly how many "false discoveries"—incorrect branches or missing species—they might be adding to their final tree, ensuring that this error rate stays below a specific, safe limit. This method is powerful because it works even when the trees in the collection are incomplete, missing some species, or have different levels of detail, a common reality in modern datasets that older methods struggle to handle.

To understand how this works, imagine trying to find the most reliable path through a dense forest where every explorer has drawn a slightly different map. Some maps show a bridge where others show a river; some include a mountain that others omit. The researchers' approach involves starting with a blank slate and slowly adding features—like a specific bridge or a mountain peak—only if the majority of the explorers agree that it belongs there. Crucially, they have built a system that acts like a strict gatekeeper. Before adding any new feature to the final map, the system checks if the evidence is strong enough to rule out the possibility that the feature is a mistake. If the evidence is weak, the feature is left out, even if it appears in many of the individual maps. This ensures that the final map is not just a popular opinion, but a structure where every part has been vetted for reliability.

The researchers tested this new method using computer simulations to see how it performed under various conditions. They created thousands of fake evolutionary histories with known truths and then tried to recover those truths using their algorithm. They found that the method successfully kept the rate of false discoveries very low, often well below the target limit they set. In cases where the data was very noisy or the trees were highly variable, the method became more conservative, choosing to leave out uncertain branches rather than risk adding a wrong one. This behavior is a feature, not a bug; it means the method prioritizes accuracy over completeness, ensuring that what remains in the final tree is highly trustworthy. The simulations also showed that as the researchers added more data, the method became better at recovering the true structure of the tree without sacrificing its safety standards.

The team then applied their method to a real-world mystery: the origins of complex life. Scientists believe that eukaryotes, the group of organisms that includes humans, animals, and plants, evolved from a bacterium being engulfed by an ancient archaeon more than two billion years ago. A major question in this field is identifying the closest living relatives of that ancient archaeal ancestor. Previous studies using standard methods have produced trees with very high confidence scores, suggesting they know exactly which group of ancient organisms is the ancestor. However, these high-confidence results have been fragile; changing the data slightly often causes the conclusions to flip entirely.

Using a dataset of 85 different gene trees shared between archaea and eukaryotes, the researchers applied their new method to reconstruct the evolutionary history. The resulting tree confirmed many well-known divisions in the tree of life, showing that the method works for established facts. However, when it came to the specific question of which group of ancient archaea is the direct ancestor of eukaryotes, the method revealed a different story. While the tree showed a strong connection to a group known as the Asgard archaea, it indicated that the data was not yet strong enough to pinpoint the single most recent ancestor with certainty. Unlike previous methods that might have forced a single answer with high confidence, this approach highlighted the uncertainty, showing that the evidence is insufficient to distinguish between the leading candidates. This result does not mean the answer is unknown forever, but rather that the current data does not support a definitive conclusion, providing a more honest and stable picture of what we know and what we still need to learn.

The significance of this work extends beyond just finding the right tree. It offers a new way to think about uncertainty in complex data. By treating the structure of the tree as a collection of features that can be tested individually, the researchers have created a tool that can handle the messy, incomplete nature of real-world data. Whether the data comes from ancient genes, social networks, or medical records, the method provides a way to summarize complex information without overpromising. It allows scientists to say, with statistical confidence, that a specific connection is real, or conversely, that the data is too weak to decide. In a scientific landscape often crowded with conflicting results, this ability to control errors and measure stability offers a clearer path forward for understanding the deep history of life and the complex structures that define our world.

Technical Summary: Consensus Tree Estimation with False Discovery Control via Partially Ordered Sets

Problem Statement

The estimation of a consensus tree (or summary tree) from a collection of tree-valued data presents significant challenges distinct from vector-valued data analysis. Tree data arises in diverse fields such as evolutionary biology, linguistics, and network analysis, where hierarchical structures organize categories. Key difficulties include:

Super-exponential Sample Space: The number of possible trees grows super-exponentially with the number of leaves, making it common for no single tree to be observed more than once in a sample.
Non-Identical Leaf Sets and Resolutions: Modern datasets often contain trees with varying leaf labels (missing taxa) and varying degrees of resolution (non-binary vs. binary trees).
Lack of Finite-Sample Guarantees: Existing methods, such as split thresholding (majority rule) or Fréchet means, often rely on asymptotic consistency or assume a common leaf set. They generally lack finite-sample guarantees for accuracy or formal control over false discoveries.
Uncertainty Quantification: Conventional support measures (e.g., bootstrap support) can indicate high confidence even when splits are unstable to small data perturbations.

The paper frames the consensus tree estimation problem as a structured feature-selection problem, where leaves and edges (splits) are treated as features. The goal is to estimate a summary tree that controls the rate of false discoveries (features included in the estimate that are not supported by the underlying population distribution) at a nominal level.

Methodology

1. Partially Ordered Set (Poset) Framework

The authors introduce a graded poset $\mathcal{P} = (\mathcal{T}, \preceq)$ to organize the space of all possible trees (including binary, non-binary, and those with missing leaves).

Elements: The set $\mathcal{T}$ includes a special least element $T_0$ (representing completely unresolved star trees) and all trees with non-empty split sets where internal nodes have degree $\ge 3$ .
Partial Order ( $\preceq$ ): A tree $T_a \preceq T_b$ if $T_b$ preserves all leaves and splits of $T_a$ while potentially adding new ones. Specifically, $T_b$ covers $T_a$ if $T_b$ is obtained by adding exactly one leaf or one split to $T_a$ while maintaining structural compatibility.
Rank Function: A rank function $rank(T)$ is defined to measure structural complexity: $rank(T) = |S(T)| + |L(T)| - 4$ for $T \neq T_0$ , and $0$ for $T_0$ . This quantifies the information content (number of splits and leaves) relative to the minimal element.

2. Similarity and Discovery Metrics

To define true and false discoveries, the authors define a similarity metric $\rho(T_1, T_2)$ based on the maximal common structure between two trees within the poset.

Maximal Common Structure: The set of elements in $\mathcal{T}$ that are less than or equal to both $T_1$ and $T_2$ with the maximum rank.
True Discoveries (TD): Defined as $\rho(\hat{T}, T^*)$ , where $\hat{T}$ is the estimate and $T^*$ is the population tree. This represents the complexity of the shared structure.
False Discoveries (FD): Defined as $rank(\hat{T}) - \rho(\hat{T}, T^*)$ . This counts the "extra" complexity in the estimate not supported by the population tree.
Error Rates: The paper defines Family-Wise Error Rate (FWER) and False Discovery Rate (FDR) based on the probability and expectation of $FD > 0$ and the False Discovery Proportion (FDP), respectively.

3. Estimation Algorithm (Algorithm 1)

The proposed method constructs a consensus tree by traversing a path in the poset from the least element $T_0$ to a maximal element, adding features only when supported by the data.

Data Splitting: The dataset $D$ is split into $D_1$ (to select a subposet $\mathcal{P}_{sub}$ ) and $D_2$ (for estimation).
Path Construction: Starting at $T_0$ , the algorithm iteratively selects a covering pair $(T_a, T_b)$ such that $T_b$ covers $T_a$ and the test statistic $score_{D_2}(T_a, T_b)$ exceeds a threshold $\gamma(T_a, T_b)$ .
Test Statistic: $score_{D_2}(T_a, T_b)$ is the proportion of trees in $D_2$ for which the similarity to $T_b$ is strictly greater than the similarity to $T_a$ . This measures support for the specific feature added in the transition from $T_a$ to $T_b$ .
Thresholding: The threshold $\gamma$ is chosen based on combinatorial quantities derived from the poset structure (specifically, the size of the largest antichain of covering pairs) and concentration inequalities (Hoeffding's inequality). This ensures FWER or FDR control at a user-specified level $q$ , even without assumptions on the data-generating process or independence of tests.

4. Feature Stability

Beyond global error control, the method provides a feature-specific stability score $\pi_{edge, D}(e; T)$ . This score measures the proportion of sample trees for which collapsing an edge $e$ in a candidate tree $T$ strictly reduces the similarity to the sample tree. This allows for the assessment of individual leaf or split stability, accommodating non-identical leaf sets and non-binary trees.

Key Contributions

First Formal False Discovery Control for Trees: The paper provides the first consensus tree estimator with rigorous finite-sample guarantees for controlling FWER and FDR.
Poset-Based Framework for Tree Estimation: It introduces a novel graded poset structure that naturally handles trees with unequal leaf sets and varying resolutions (binary vs. non-binary), overcoming limitations of existing methods that require common leaf sets.
Model-Free Guarantees: The error control guarantees are agnostic to the tree-generating process, relying only on the structural properties of the poset and the data-splitting strategy.
Stability Scores: The method yields interpretable stability scores for individual features (leaves and splits), offering a more nuanced view of uncertainty than traditional bootstrap support.
Algorithmic Implementation: It proposes a computationally feasible algorithm (Algorithm 1) that navigates the super-exponential tree space by growing a path through a subposet, utilizing combinatorial bounds to control error rates.

Results

Simulation Study

The authors evaluated the method using 300 independent replicates across various settings involving:

Sample Sizes: $n \in \{50, 100, 300\}$ .
Dispersion: Varying levels of noise ( $\delta$ ) in the data-generating process (modeled as a random walk on BHV tree space).
Tree Topologies: Resolved (caterpillar, balanced) and unresolved population trees.
Leaf Coverage: Settings with complete and incomplete taxon coverage.

Findings:

FDR Control: The procedure successfully controlled the empirical FDR below the nominal level ( $q=0.1$ ) across all settings. In many cases, the estimated FDR was zero.
Trade-offs: As expected, higher dispersion ( $\delta$ ) led to lower True Discovery Rates (TDR) and higher FDR. However, increasing sample size ( $n$ ) significantly improved TDR, even in high-dispersion scenarios.
Topology Effects: Splits in "balanced" trees were harder to recover than in "caterpillar" trees due to the combinatorial frequency of small vs. large partitions, a phenomenon the method captured accurately.
Robustness: The method remained robust even when population trees were unresolved, correctly identifying that adding binary resolutions to unresolved nodes constitutes a false discovery.

Real Data Application: Origin of Eukaryotic Life

The method was applied to 85 gene trees derived from 15 organisms (including Asgard archaea and eukaryotes) to investigate the evolutionary origins of complex life.

Comparison: The estimated consensus tree (with FDR control at $q=0.1$ ) was compared against majority rule, quartet maximization, and maximum likelihood trees.
Findings: The estimated tree recapitulated well-known divisions but highlighted a critical uncertainty: there is insufficient data to determine the most recent archaeal ancestor of eukaryotic life.
Stability: Unlike other methods that showed high bootstrap support for specific branching orders, the proposed method's stability scores indicated that the placement of the eukaryotic ancestor within the Asgard clade was not robustly supported by the available gene data. This suggests that previous high-confidence claims may be sensitive to data perturbations.

Significance and Claims

The paper claims to provide a foundational framework for integrating multiple testing tools into tree estimation. By recasting tree estimation as a feature selection problem on a poset, the authors offer:

Rigorous Uncertainty Quantification: A shift from asymptotic consistency or heuristic support measures to finite-sample, model-free error control.
Handling of Real-World Data: A practical solution for the common issue of unequal leaf sets and non-binary branching, which often impedes existing consensus methods.
Interpretability: The ability to assign stability scores to specific features allows researchers to distinguish between well-supported evolutionary signals and noise, as demonstrated in the analysis of ancient gene trees.

The authors emphasize that their approach is not limited to phylogenetics but is applicable to any domain involving collections of hierarchical data objects. They maintain a modest stance, noting that while the method controls error rates, the power to recover true features depends on sample size and the inherent signal-to-noise ratio of the data.