📊 statistics

Detecting Jumps on a Tree: a Hierarchical Normalized Stable Process Model for Evolution of Discrete Distributions

This paper proposes a nonparametric Bayesian model based on a hierarchical normalized stable process and a Poisson process to detect distributional jumps on tree-structured populations, such as phylogenetic trees, by leveraging shared statistical information across subpopulations and employing an efficient particle MCMC algorithm for posterior inference.

Original authors: Hanxi Sun, Heejung Shim, Vinayak Rao

Published 2026-09-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hanxi Sun, Heejung Shim, Vinayak Rao

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 a vast, branching story written in the DNA of every species. Scientists have long used these family trees, known as phylogenetic trees, to trace how different groups of organisms are related and how they have changed over time. Imagine a tree where the trunk represents the oldest common ancestor and the twigs at the very top represent the species alive today. For decades, researchers have tried to understand how specific traits, like a virus's ability to evade the immune system or a language's way of describing family life, evolve as you move from the trunk to the tips. The traditional view often assumed these changes happened slowly and steadily, like a gentle drift. However, evolution can also be punctuated by sudden, sharp shifts where a population's characteristics change abruptly. Detecting these sudden shifts is difficult because the data is often messy, with many species having very few recorded examples, making it hard to tell if a change is real or just a fluke of sampling.

A team of statisticians at Purdue University and the University of Melbourne has developed a new way to spot these sudden shifts on evolutionary trees. Their work focuses on a method that treats the evolution of traits not as a single smooth line, but as a series of potential jumps. They built a sophisticated computer model that looks at the entire tree at once, allowing it to borrow strength from related groups to make better guesses about where changes occurred. Instead of assuming that every branch evolves in isolation, their model understands that a group of species is likely to be similar to its close relatives unless a specific event caused a change. By combining this idea with a mathematical tool that handles uncertainty gracefully, they created a system that can identify exactly where on the tree these jumps happened, even when the data is sparse or the changes are very subtle.

The researchers tested their approach using both made-up data and real-world examples to see how well it worked compared to existing methods. In one set of tests, they created synthetic trees with known jumps and found that their method was far better at spotting small, gradual changes than previous tools, which often missed them entirely. When the changes were large and obvious, both methods performed well, but the new approach showed a distinct advantage when the signal was weak. This is crucial because in the real world, evolutionary shifts are often small and hard to detect. The team then applied their model to a real dataset involving a virus and human immune systems. They analyzed a tree built from the genetic sequences of 261 viruses and looked for changes in how often a specific immune marker appeared. Their model successfully identified a specific branch where the frequency of this marker jumped significantly, confirming a finding made by other researchers but doing so with a more robust statistical framework that accounts for the tree's structure.

In another real-world application, the team examined the social customs of the Uto-Aztecan language family, specifically how newly married couples choose where to live. This data is more complex than a simple yes-or-no answer, as it involves four different categories of residence. The researchers found strong evidence for two distinct jumps in the tree. The first jump marked a shift toward couples establishing their own independent households, a change that likely reflected the need to find new farmland in poor soil regions. The second jump indicated a shift toward living with the wife's family or a mix of arrangements, corresponding to a move into desert and plains environments. The model calculated a very high probability that these two changes were real and not just random noise, pinpointing exactly which branches of the language tree held these new social patterns.

The core of this new method lies in how it handles the relationships between different parts of the tree. Unlike older models that treated each jump as an independent event, this approach links the changes together. It assumes that if a change happens on one branch, the next branch is likely to start from that new state rather than resetting to a default. This allows the model to share information across the tree; if one group of species has very little data, the model can look at its neighbors to make a more informed decision. The researchers also developed a fast computer algorithm to run these complex calculations, ensuring that the method is practical for large datasets. By treating the tree as a connected hierarchy rather than a collection of isolated points, they were able to uncover evolutionary stories that were previously hidden in the noise of the data.

The results suggest that this hierarchical approach offers a more reliable way to study how traits evolve, particularly when the changes are small or the data is limited. The team demonstrated that their method could detect subtle shifts that other tools missed, providing a clearer picture of evolutionary history. While the current work focuses on traits that fall into distinct categories, the authors note that the framework could eventually be adapted for continuous traits, like body size or temperature, and could even account for uncertainty in the shape of the tree itself. For now, the method stands as a powerful tool for biologists and linguists alike, offering a sharper lens through which to view the branching paths of life and culture.

Technical Summary: Detecting Jumps on a Tree via Hierarchical Normalized Stable Processes

Problem Formulation
This work addresses the problem of clustering populations arranged in a hierarchical tree structure, specifically focusing on phylogenetic trees where nodes represent biological species or language communities. The core objective is to identify "jumps"—branches where the probability distribution of observations at a parent node differs significantly from that of its child. Unlike traditional phylogenetic comparative methods that often assume a single phenotype per species or model evolution as a continuous diffusion process (e.g., Brownian motion), this paper models the evolution of entire discrete distributions. The goal is to detect abrupt changes in these distributions and segment the tree accordingly, accommodating scenarios where multiple observations exist per node and where distributions may be non-binary.

Methodology
The authors propose a fully nonparametric Bayesian model built upon two primary stochastic processes: a Poisson process for jump locations and a Hierarchical Normalized Stable Process (HNSP) for the distributions themselves.

Poisson Process Jumps: Changes in distribution are modeled as occurring at a random, finite set of points $J$ along the continuous tree. To prevent the aggregate jump intensity from artificially increasing with tree depth (due to the exponential growth of branches), the Poisson rate is calibrated such that the intensity remains constant across depth. This is achieved by rescaling branch lengths based on the number of branches at a given depth.
Hierarchical Normalized Stable Process (HNSP): The distributions $G_v$ at each node are modeled as random probability measures. The model utilizes the Normalized Stable Process (NSP), a generalization of the Dirichlet process. Crucially, the HNSP is constructed hierarchically: the distribution at a jump point $j$ is drawn from an NSP centered on the distribution of its immediate parent jump point ( $G^*_j \sim \text{NSP}(d, G^*_{pa(j)})$ ). This contrasts with previous approaches (e.g., treeBreaker) where new distributions are drawn independently of their predecessors. This dependency allows the model to "borrow statistical strength" across the tree, enabling the detection of subtle, aligned distributional changes even when data at specific nodes are sparse.
Pruning and Marginalization: The model introduces an equivalence relation where nodes connected by a path without jumps share the same distribution. This allows the original tree to be "pruned" into a smaller tree $T_J$ $T_{J}$ where each node represents a cluster of populations with a shared distribution.
- Intermediate Jumps: A key technical contribution is the marginalization of intermediate jumps (jumps that do not immediately precede an observed node). Using properties of the NSP, the authors show that a sequence of $b$ jumps on a branch can be marginalized out, resulting in a single NSP with a discount parameter scaled by $d^b$ .
- Chinese Restaurant Franchise (CRF): To handle the infinite-dimensional nature of the distributions, the authors employ a Chinese Restaurant Franchise representation. This allows the model to integrate out the latent distributions $G^*_v$ , representing observations as finite sequences of cluster assignments along the path to the root.
Posterior Inference: Inference is performed using a Particle Markov Chain Monte Carlo (PMCMC) algorithm. Since the marginal likelihood $p(D|b)$ is intractable due to the summation over latent CRF configurations, the authors use a Sequential Monte Carlo (particle filter) to generate an unbiased estimator of the likelihood. This estimator is then used within a pseudo-marginal Metropolis-Hastings framework to sample the jump configuration $b$ and the Poisson rate $\lambda$ .

Key Contributions

Nonparametric Flexibility: The model places priors directly on infinite-dimensional probability distributions, allowing for complex, multimodal, and non-standard phenotype distributions without strong parametric assumptions.
Hierarchical Dependency: By centering child distributions on parent distributions rather than drawing them independently, the model effectively shares statistical strength across the tree, improving inference in data-sparse regimes.
Computational Tractability: The development of a marginalization scheme for intermediate jumps and the use of the CRF representation enable efficient posterior inference via particle MCMC, overcoming the computational challenges of nonparametric models on trees.
Generalization: The framework accommodates binary and non-binary data, multiple observations per node, and observations at internal nodes (e.g., fossil data), extending beyond the capabilities of existing methods like treeBreaker.

Experimental Results
The authors evaluate the method on both synthetic and real-world datasets:

Synthetic Data: In simulations with binary traits, the proposed method significantly outperforms treeBreaker in detecting small jumps (low total variation distance), achieving an Area Under the Curve (AUC) of 0.80 compared to 0.50 for treeBreaker at low signal strength. As the jump size increases, both methods perform well, but the proposed method maintains a competitive edge.
HLA Allele Data: Applied to a viral phylogenetic tree and HLA allele B57 presence/absence data, the method successfully identified a jump in distribution consistent with previous findings by treeBreaker, detecting a clade with a high prevalence of the allele.
Uto-Aztecan Language Data: Applied to a dataset of post-marital residence practices (four categories), the method detected two significant jumps in the language tree. These jumps corresponded to shifts in social practices (e.g., from patrilocality to neolocality, and later to matrilocality/ambilocal), demonstrating the model's ability to handle multi-category discrete data.

Significance and Claims
The paper claims that its primary contribution lies in the ability to detect jumps in evolving discrete distributions on trees by leveraging hierarchical dependencies between distributions. The authors argue that their hierarchical approach provides a more robust mechanism for statistical sharing than independent jump models, particularly when changes are gradual or data is limited. They position the work as a flexible, nonparametric alternative to existing phylogenetic trait association methods, capable of handling complex data structures (non-binary traits, internal node observations) while providing a principled Bayesian framework for segmentation and hypothesis testing (via Bayes factors). The authors note that while they focus on pure-jump evolution, the framework offers a potential pathway for modeling gradual evolution by jointly tuning discount parameters and jump rates.

Technical Summary: Detecting Jumps on a Tree via Hierarchical Normalized Stable Processes

More like this