Bayesian hidden Markov tree models for clustering genes with shared evolutionary history

Yang Li, Shaoyang Ning, Sarah E. Calvo, Vamsi K. Mootha, Jun S. Liu

TL;DR

CLIME (CLustering by Inferred Models of Evolution) uses a Bayesian tree-structured Hidden Markov Model to group genes that share a history of being gained or lost together across species. By accounting for the branching structure of evolution and the inherent uncertainty in phylogenetic trees, CLIME identifies functional gene modules far more accurately than traditional distance-based metrics.

What Problem Does This Paper Address?

In biology, "guilt by association" is a powerful tool: if we don't know what a gene does, we look at its "friends"—genes it frequently interacts with. One way to find these friends is through phylogenetic profiling, which tracks the presence or absence of genes across different species. The logic is simple: if two genes are always gained or lost together over millions of years, they likely work together in the same biological pathway.

However, traditional methods for analyzing these profiles (like Hamming distance or Pearson correlation) have major flaws:

  1. Independence Assumption: they treat every species as an independent data point, ignoring the fact that species are related through a tree-like evolutionary history.
  2. Noise Sensitivity: they struggle with "noisy" data caused by sequencing errors or incomplete genome annotations.
  3. Fixed Trees: they usually rely on a single "best guess" evolutionary tree, even though our understanding of evolutionary history is often uncertain.

Methods

The authors present CLIME 1.0 and an improved CLIME 1.1. The core of the approach is a Bayesian mixture of tree-structured Hidden Markov Models (HMMs).

  • Tree-structured HMM: Instead of a linear sequence, the HMM follows the branches of a phylogenetic tree. Each node represents a species (extant or ancestral), and the "hidden state" is the presence or absence of a gene. Transitions represent evolutionary gain or loss events.
  • Dirichlet Process (DP) Prior: This is a "non-parametric" clustering technique. It allows the model to automatically infer the number of gene clusters (Evolutionary Conserved Modules, or ECMs) from the data, rather than requiring the user to specify a number upfront.
  • Gibbs Sampling: The authors use this MCMC (Markov Chain Monte Carlo) technique to sample from the complex posterior distribution of the model, allowing them to estimate cluster assignments and evolutionary parameters.
  • Handling Uncertainty (CLIME 1.1): While version 1.0 uses a fixed tree, version 1.1 incorporates a prior distribution over multiple possible tree structures. This makes the model robust to errors in the underlying phylogenetic tree.
  • The Two-Step Process:
    1. Partition: Cluster a known set of genes into modules.
  • Expansion: Use a Log-Likelihood Ratio (LLR) to scan the rest of the genome and find new genes that fit the "evolutionary signature" of those modules.

Datasets

The researchers evaluated CLIME using:

  • Simulated Data: Sets of 50 genes across 139 species, generated using both tree-based and tree-independent models to test robustness.
  • Human Genome Reference: A matrix of 20,834 human protein-coding genes across 139 eukaryotic species.
  • Biological Benchmarks:
    • 44 genes from the Mitochondrial Respiratory Chain Complex I.
  • 194 genes from the Proteinaceous Extracellular Matrix.
  • 409 manually curated gene sets from OMIM (Online Mendelian Inheritance in Man), related to specific genetic diseases.

Key Insights and Ideas

  • Evolution is Not a Flat List: By modeling the tree structure, CLIME recognizes that a gene loss in a common ancestor is a single event, whereas traditional metrics would count it as multiple independent losses in all descendant species, leading to skewed results.
  • Embracing the "Shaky Ground": The jump from CLIME 1.0 to 1.1 is significant. By treating the phylogenetic tree as a distribution rather than a fixed fact, the model avoids "overfitting" to a potentially incorrect evolutionary history.
  • The Power of LLR: Using a Log-Likelihood Ratio against a "background null model" (the average loss rate across the whole genome) allows CLIME to filter out genes that appear to co-evolve simply because they are "old" or "common," focusing instead on specific shared histories.

Key Results

  • Superior Accuracy: In simulations, CLIME 1.1 consistently achieved higher Adjusted Rand Index (ARI) scores than Hamming distance or Pearson correlation, especially when noise was high or the tree was misspecified.
  • Complex I Discovery: CLIME correctly partitioned the 44 genes of Mitochondrial Complex I into functional sub-clusters. In the "Expansion" phase, it identified several assembly factors that were not in the original set but are known to be essential for the complex.
  • Ciliary Disease Validation: When applied to genes related to ciliary dyskinesia, CLIME identified an ECM with a very high "strength" score. Its expansion list contained 100 novel candidates; 50 of these were already validated in the "Ciliome" database, proving the model's predictive power.

Limitations and Future Work

  • Fixed Error Rates: Currently, the observation error rate ($q$) is fixed at 1% based on biological intuition. The authors note that estimating this directly from the data would be more statistically rigorous.
  • Computational Cost: The Gibbs sampler is computationally intensive. While it handles 100 genes in 30 minutes, scaling to the entire genome for the "Partition" step remains a challenge ($O(Sn^2)$ complexity).
  • Species-Specific Noise: The model assumes the same error rate across all species, but some genomes are sequenced much more accurately than others. Future versions could incorporate species-specific mis-observation rates.

Summary updated

Abstract

Determination of functions for poorly characterized genes is crucial for understanding biological processes and studying human diseases. Functionally associated genes are often gained and lost together through evolution. Therefore identifying co-evolution of genes can predict functional gene-gene associations. We describe here the full statistical model and computational strategies underlying the original algorithm CLustering by Inferred Models of Evolution (CLIME 1.0) recently reported by us (Cell 158 (2014) 213–225). CLIME 1.0 employs a mixture of tree-structured hidden Markov models for gene evolution process, and a Bayesian model-based clustering algorithm to detect gene modules with shared evolutionary histories (termed evolutionary conserved modules, or ECMs). A Dirichlet process prior was adopted for estimating the number of gene clusters and a Gibbs sampler was developed for posterior sampling. We further developed an extended version, CLIME 1.1, to incorporate the uncertainty on the evolutionary tree structure. By simulation studies and benchmarks on real data sets, we show that CLIME 1.0 and CLIME 1.1 outperform traditional methods that use simple metrics (e.g., the Hamming distance or Pearson correlation) to measure co-evolution between pairs of genes.
BibTeX
@article{li2019bayesian,
  author = {Yang Li and Shaoyang Ning and Sarah E. Calvo and Vamsi K. Mootha and Jun S. Liu},
  title = {{Bayesian hidden Markov tree models for clustering genes with shared evolutionary history}},
  journal = {The Annals of Applied Statistics},
  year = {2019},
  doi = {10.1214/18-aoas1208},
}

Loading related content...

Figure