Detecting coevolution without phylogenetic trees? Tree-ignorant metrics of coevolution perform as well as tree-aware metrics

J. Gregory Caporaso, Sandra Smit, Brett C Easton, Lawrence Hunter, Gavin Huttley, Rob KnightBMC 2008 · DOI

TL;DR

This paper introduces a novel statistical transformation that allows "tree-ignorant" coevolution detection methods to perform as well as computationally expensive "tree-aware" methods. This breakthrough significantly speeds up coevolutionary analysis, making large-scale proteome-wide studies more feasible and offering new avenues for understanding protein structure, function, and interactions.

What Problem Does This Paper Address?

Identifying coevolving positions in biological sequences is crucial for understanding protein structure, predicting interactions, and pinpointing functionally important regions. Coevolutionary analysis aims to find pairs of amino acid positions that tend to change together across evolutionary history, suggesting they are functionally linked.

Traditionally, methods for detecting coevolution fall into two camps: "tree-aware" methods that explicitly incorporate phylogenetic information (the evolutionary history of the sequences) and "tree-ignorant" methods that do not. Tree-aware methods are generally considered more accurate because they can distinguish true coevolution from patterns driven by shared ancestry (i.e., two positions evolving similarly because their common ancestor had those traits). However, tree-aware methods are computationally very demanding, often taking days or weeks to run on large datasets.

Tree-ignorant methods, on the other hand, are much faster but have been criticized for potentially conflating shared ancestry with coevolution, leading to false positives. The authors hypothesized that by using a statistical framework that appropriately controls for the signal of shared ancestry, tree-ignorant methods could achieve the same statistical power as tree-aware methods, but with a massive speed advantage.

Methods

The core innovation of this paper is a t-test transformation applied to coevolution metrics. This transformation creates a null distribution that accounts for shared ancestry, allowing tree-ignorant metrics to be compared against it. This effectively "controls for shared ancestry" without needing to explicitly build a phylogenetic tree.

The authors systematically compared nine coevolution algorithms:

  • Tree-ignorant methods: Mutual Information (MI), Normalized Mutual Information (NMI), Resampled Mutual Information (RMI), Statistical Coupling Analysis (SCA), and Corrected Mutual Information (MIp).
  • Tree-aware methods: LnLCorr, Ancestral States (AS), Generalized Continuous-Time Markov Process Coevolutionary Algorithm (GCTMPCA), and CoMap.

They also investigated the impact of reduced-state amino acid alphabets. These alphabets collapse the 20 standard amino acids into fewer categories based on physicochemical properties (e.g., charge, polarity, size). This is a common practice to reduce computational complexity and potentially increase statistical power, but the authors explored whether it truly improves performance and how the choice of alphabet affects results.

Datasets

The study used two primary biological datasets:

  1. Tetrapod Myoglobin: A dataset of 42 sequences, approximately 153 positions long, known to be largely alpha-helical.
  2. Chordate Myosin Rod Domain: A larger dataset of 114 sequences, approximately 1064 positions long, also predominantly alpha-helical.

To serve as negative controls, the authors created randomized versions of these alignments by shuffling the order of columns. This process removes all structural information and thus any expected coevolutionary signal related to protein structure.

Key Insights and Ideas

  • Shared ancestry is the main confounder: The paper strongly suggests that the primary challenge in coevolutionary analysis is disentangling true coevolution from patterns driven by common ancestry.
  • A statistical "trick" can level the playing field: The t-test transformation is a powerful tool that can make tree-ignorant methods as effective as tree-aware ones by providing a statistically sound null distribution that accounts for evolutionary history.
  • Speed matters: The massive computational advantage of tree-ignorant methods, combined with their comparable performance after transformation, makes them the preferred choice for large-scale, genome-wide coevolutionary studies.
  • Alphabet choice is critical, but not always straightforward: While reduced alphabets can improve performance, especially for specific interaction types (like charge-based interactions in alpha helices), the "correct" alphabet is not always obvious. Using the full alphabet can be a safer default when the interaction type is unknown.

Key Results

  • Tree-ignorant methods outperform tree-aware methods: In the myoglobin dataset, transformed tree-ignorant metrics (particularly MI) often showed statistically significant results for detecting alpha-helix periodicity where tree-aware methods did not.
  • No significant difference in statistical power: After the t-test transformation, tree-ignorant methods demonstrated comparable or superior statistical power to tree-aware methods in identifying coevolving pairs in alpha helices.
  • Computational efficiency: Tree-ignorant methods were orders of magnitude faster than tree-aware methods, with some tree-aware methods being computationally prohibitive for larger datasets like the myosin rod.
  • Alphabet impact: Charge-based alphabets were particularly effective for identifying stabilizing interactions in alpha helices. However, performance was not always improved by recoding, highlighting the importance of choosing an appropriate alphabet. For example, using a "size" alphabet instead of a "charge" alphabet could obscure coevolutionary signals related to charge.

Limitations and Future Work

  • T-test assumptions: The authors acknowledge that the distance matrix structure of coevolution scores violates the independence assumption of the t-test. However, they validated their results using a non-parametric matrix permutation test and found the t-test to be robust.
  • Defining "true positives": Biologically relevant evaluations of coevolution algorithms are difficult because it's hard to definitively know which pairs of positions truly coevolve. The study relied on the known periodicity of alpha helices as a proxy for coevolution.
  • Alphabet optimization: While the study explored various alphabets, optimizing alphabet choice for a specific dataset can be computationally intensive and may not always be feasible in large-scale analyses.
  • Future work: The authors suggest that further investigation into the "true positives" and the development of methods that can robustly identify coevolutionary signals across diverse protein families and interaction types would be valuable. They also highlight the potential for these faster, more accurate methods to unlock new insights into protein evolution on a massive scale.

Summary updated

Abstract

The results suggest that t-test transformation of tree-ignorant metrics can be sufficient to control for patterns arising from shared ancestry.
BibTeX
@inproceedings{caporaso2008detecting,
  author = {J. Gregory Caporaso and Sandra Smit and Brett C Easton and Lawrence Hunter and Gavin Huttley and Rob Knight},
  title = {{Detecting coevolution without phylogenetic trees? Tree-ignorant metrics of coevolution perform as well as tree-aware metrics}},
  booktitle = {BMC},
  year = {2008},
  doi = {10.1186/1471-2148-8-327},
}
Figure