Testing for dependence on tree structures

Merle Behr, M. Azim Ansari, Axel Munk, Chris Holmes

TL;DR

This paper introduces treeSeg, a novel statistical method and R package for rigorously testing associations between hierarchical tree structures (like phylogenetic trees or clustering dendrograms) and measured response variables. It addresses the common challenge of finding meaningful group structures within data by providing a statistically guaranteed way to identify segments of the tree that exhibit distinct response patterns, enhancing reproducibility in fields like genomics and bioinformatics.

What Problem Does This Paper Address?

In many scientific disciplines, data is organized hierarchically, often represented by tree structures. Examples include phylogenetic trees showing evolutionary relationships, hierarchical clustering dendrograms summarizing sample similarities, and language evolution trees. A frequent question is whether a measured response variable (e.g., a gene's expression level, a patient's phenotype) is associated with these latent group structures within the tree.

The current approach to answering this question is often ad hoc. Researchers typically manually inspect the tree, decide on a number of "clusters" or segments to examine, and then test for associations. This subjective process lacks statistical rigor, can be difficult to reproduce, and may miss important associations at different levels of the hierarchy. The paper aims to fill this gap by providing a statistically sound, high-power method that tests for associations across all levels of a given tree structure while controlling the overall false positive rate.

Methods

The core of treeSeg is a multiscale change-point detection framework adapted for tree structures. Instead of a linear sequence, the method operates on the branching nature of a tree. It treats the input tree as fixed and tests whether the response variable distribution depends on the sample's position within this tree.

Key aspects of the methodology include:

  • Embedding in Change-Point Detection: The problem of segmenting a tree based on response distributions is reframed as a multiscale change-point problem.
  • Likelihood Ratio Statistics: The method employs likelihood ratio (LR) statistics to test for changes in response distributions at various levels of the tree hierarchy.
  • Multiple Testing Correction: A crucial contribution is the rigorous control of the overall false positive error rate across all tested segments and levels of the tree. This is achieved by carefully selecting significance levels for individual tests.
  • Confidence Sets and Bands: treeSeg not only identifies the most likely segmentation but also provides confidence sets for the nodes associated with changes in response distribution and confidence bands for the estimated response probabilities within segments.
  • Robustness: The method is designed to be robust to how the tree is generated and can handle missing data, with predictions for new samples also possible.

Datasets

The paper uses a publicly available breast cancer gene expression dataset for its application example. The gene expression data was used to build a hierarchical clustering tree based on sample correlations. Six clinical responses were then analyzed against this tree structure. No new benchmark datasets were introduced.

Key Insights and Ideas

  • Bridging Ad Hoc Methods and Rigor: treeSeg provides a much-needed statistical foundation for a common exploratory analysis task, moving beyond subjective visual inspection to robust hypothesis testing.
  • Multiscale Discovery: The method's ability to test associations at all levels of the tree hierarchy is a significant advantage, potentially uncovering relationships missed by manual inspection focused on a single level.
  • Guaranteed Error Control: The statistical guarantees regarding the false positive error rate are critical for ensuring the reliability and reproducibility of findings.
  • Uncertainty Quantification: Providing confidence sets and bands allows researchers to understand the uncertainty associated with the detected segments and estimated response probabilities, enhancing interpretability.

Key Results

  • Simulated Data: Simulations demonstrated that treeSeg has high power to detect associations between response variables and tree structures, with a very low rate of false positives (e.g., correctly detecting no association in 98.6% of runs for random trees).
  • Cancer Data Application: When applied to the breast cancer dataset, treeSeg identified distinct response patterns for several clinical variables. For one response (angioinvasion), it found no association with the tree structure, a finding that contrasts with some other responses. For another response (histological grade), it identified two clusters with distinct distributions, aligning with previous visual analysis but providing statistical validation. The method also revealed different association patterns for other responses compared to prior ad hoc analyses.
  • Computational Efficiency: The R package treeSeg is computationally efficient, scaling well with sample size. A test with 100,000 leaves took approximately 110 minutes on a standard laptop.

Limitations and Future Work

  • Tree Structure as Input: treeSeg requires a pre-defined tree structure as input. While it can handle noisy tree structures to some extent, significant deviations between the input tree and the true underlying structure could impact results. The authors suggest that if the input tree is a reasonably accurate representation of the neighborhood structure, the output is robust.
  • Tuning Parameter: The primary tuning parameter is the significance level α. Users can choose different values of α to balance the trade-off between detecting more clusters (higher α) and increasing the risk of false positives (lower α for higher confidence).
  • Future Directions: The paper highlights the method's ubiquitous applicability across various scientific fields. Future work could explore extensions to more complex tree types or incorporate dynamic tree structures. The authors also mention that further theoretical work could investigate improving segmentation rates under specific tree structural assumptions.

Summary updated

Abstract

Tree structures, showing hierarchical relationships and the latent structures between samples, are ubiquitous in genomic and biomedical sciences. A common question in many studies is whether there is an association between a response variable measured on each sample and the latent group structure represented by some given tree. Currently, this is addressed on an ad hoc basis, usually requiring the user to decide on an appropriate number of clusters to prune out of the tree to be tested against the response variable. Here, we present a statistical method with statistical guarantees that tests for association between the response variable and a fixed tree structure across all levels of the tree hierarchy with high power while accounting for the overall false positive error rate. This enhances the robustness and reproducibility of such findings.
BibTeX
@inproceedings{behr2020testing,
  author = {Merle Behr and M. Azim Ansari and Axel Munk and Chris Holmes},
  title = {{Testing for dependence on tree structures}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2020},
  doi = {10.1073/pnas.1912957117},
}
Figure