HyperTraPS: Inferring probabilistic patterns of trait acquisition in\n evolutionary and disease progression pathways

Sam F. Greenbury, Mauricio Barahona, Iain G. JohnstonarXiv 2019 · DOI · arXiv

Abstract

The explosion of data throughout the biomedical sciences provides unprecedented opportunities to learn about the dynamics of evolution and disease progression, but harnessing these large and diverse datasets remains challenging. Here, we describe a highly generalisable statistical platform to infer the dynamic pathways by which many, potentially interacting, discrete traits are acquired or lost over time in biomedical systems. The platform uses HyperTraPS (hypercubic transition path sampling) to learn progression pathways from cross-sectional, longitudinal, or phylogenetically-linked data with unprecedented efficiency, readily distinguishing multiple competing pathways, and identifying the most parsimonious mechanisms underlying given observations. Its Bayesian structure quantifies uncertainty in pathway structure and allows interpretable predictions of behaviours, such as which symptom a patient will acquire next. We exploit the model's topology to provide visualisation tools for intuitive assessment of multiple, variable pathways. We apply the method to ovarian cancer progression and the evolution of multidrug resistance in tuberculosis, demonstrating its power to reveal previously undetected dynamic pathways.

Introduction

In biology and medicine, many critical processes are defined by the sequential acquisition of discrete features. Examples include cancer cells accumulating chromosomal aberrations, patients developing a sequence of clinical symptoms, or bacteria gaining resistance to multiple antibiotics. Understanding these "progression pathways" is vital for precision medicine and public health. However, as the number of traits ($L$) increases, the number of possible states grows exponentially ($2^L$), creating a "curse of dimensionality" that renders traditional transition matrix calculations computationally infeasible. Furthermore, most existing tools assume a single "true" path, failing to account for the diversity of routes observed in real-world populations.

The HyperTraPS Framework

To overcome these challenges, the authors introduce HyperTraPS (Hypercubic Transition Path Sampling). This framework represents every possible combination of $L$ traits as a vertex on an $L$-dimensional hypercube. A transition from an initial state (e.g., "no traits") to a final state is modeled as a path along the edges of this cube.

The HyperTraPS workflow for longitudinal data. It transforms individual patient symptom sequences into transition matrices, which are then used to infer probabilistic pathways on a hypercubic graph, ultimately visualized as a Probabilistic Feature Graph (PFG).

Key Methodological Innovations

  • Path Sampling: Instead of exhaustive matrix calculation, HyperTraPS uses biased random walks to sample the most likely paths that explain the observed data. This allows the model to scale to dozens of traits (up to $L=65$ in tests).
  • Bayesian Inference: An advanced Markov Chain Monte Carlo (MCMC) approach estimates transition probabilities, allowing for the quantification of uncertainty in the inferred pathway structure.
  • Model Selection and Regularization: The framework uses the Akaike Information Criterion (AIC) to prune unnecessary parameters. This "Occam’s Razor" approach helps distinguish between simple independent trait acquisition and complex models where traits interact (e.g., "Trait A makes Trait B more likely").
  • Visualization: High-dimensional paths are projected into intuitive 2D "Probabilistic Feature Graphs" (PFGs), making it easy to identify where pathways diverge or converge.

Handling Diverse Data Types

HyperTraPS is highly generalizable, capable of processing cross-sectional snapshots, longitudinal sequences, and phylogenetically-linked data. In the case of phylogenetic data, the model accounts for shared ancestry to infer the order of trait acquisition across different lineages.

Application of HyperTraPS to phylogenetically-linked data. The framework accounts for shared ancestry to infer the order of trait acquisition across different species or lineages.

Key Insights and Results

The researchers validated HyperTraPS using both synthetic and real-world biomedical datasets, yielding several significant insights:

  • Bimodality and Competing Pathways: The model identified "bimodality" in trait acquisition—where certain traits are acquired either very early or very late, but rarely in between. This is a clear indicator of multiple, distinct competing pathways within a single population.
  • Ovarian Cancer Progression: Analysis of chromosomal aberrations in ovarian cancer revealed "canalization," where the first genetic mistake often dictates the subsequent progression route. HyperTraPS successfully identified pathways (such as 4q- before 5q-) that standard monotonic models often miss.
  • Tuberculosis Evolution: In a dataset of 1,000 drug-resistant TB isolates, the model mapped the evolution of multidrug resistance. It identified a common "central" pathway involving rifamycin resistance followed by compensatory mutations in rpoC, while also highlighting rarer alternative routes.
  • Predictive Power: Regularized second-order models (accounting for trait interactions) consistently provided the highest predictive likelihood in out-of-sample tests, demonstrating that these interactions are essential for accurate modeling.

Conclusion

HyperTraPS provides a powerful, scalable framework for mapping the hidden dynamics of complex biological systems. While current limitations include challenges with unknown starting states and the use of greedy regularization algorithms, the platform's ability to handle high-dimensional, diverse data makes it a significant advancement. Future work may expand the framework to multi-state traits or continuous data, further broadening its application in fields like transcriptomics and clinical symptom tracking.

Summary updated

Abstract

The explosion of data throughout the biomedical sciences provides\nunprecedented opportunities to learn about the dynamics of evolution and\ndisease progression, but harnessing these large and diverse datasets remains\nchallenging. Here, we describe a highly generalisable statistical platform to\ninfer the dynamic pathways by which many, potentially interacting, discrete\ntraits are acquired or lost over time in biomedical systems. The platform uses\nHyperTraPS (hypercubic transition path sampling) to learn progression pathways\nfrom cross-sectional, longitudinal, or phylogenetically-linked data with\nunprecedented efficiency, readily distinguishing multiple competing pathways,\nand identifying the most parsimonious mechanisms underlying given observations.\nIts Bayesian structure quantifies uncertainty in pathway structure and allows\ninterpretable predictions of behaviours, such as which symptom a patient will\nacquire next. We exploit the model's topology to provide visualisation tools\nfor intuitive assessment of multiple, variable pathways. We apply the method to\novarian cancer progression and the evolution of multidrug resistance in\ntuberculosis, demonstrating its power to reveal previously undetected dynamic\npathways.\n
BibTeX
@misc{greenbury2019hypertraps,
  author = {Sam F. Greenbury and Mauricio Barahona and Iain G. Johnston},
  title = {{HyperTraPS: Inferring probabilistic patterns of trait acquisition in\textbackslash\{\}n evolutionary and disease progression pathways}},
  year = {2019},
  eprint = {1912.00762},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.00762},
}
Figure