Tertiary-interaction characters enable fast, model-based structural phylogenetics beyond the twilight zone

Caroline Puente-Lelièvre, Ashar J. Malik, Jordan Douglas, David B. Ascher, Matthew A. B. Baker, Jane R. Allison, Anthony M. Poole, Daniel Lundin, Matthew S. Fullmer, Remco Bouckert, Hyunbin Kim, Martin Steinegger, Nicholas J. MatzkebioRxiv 2023 · DOI

TL;DR

This paper introduces a new method for protein phylogenetics that leverages 3D structural information (3Di characters) alongside traditional amino acid sequences. This approach significantly speeds up phylogenetic analysis and improves accuracy, especially for distantly related proteins where sequence similarity is low, potentially making structural phylogenetics a routine tool.

What Problem Does This Paper Address?

Traditional protein phylogenetics relies heavily on amino acid (AA) sequence similarity. However, as sequences diverge, similarity drops below 30% (the "twilight zone"), making it difficult to accurately infer evolutionary relationships. Protein structure, being more conserved than sequence, offers a promising alternative for these deep evolutionary questions. Historically, structural phylogenetics faced two main hurdles: a scarcity of solved protein structures and a reliance on distance-based methods that struggled with statistical inference and uncertainty. The advent of AlphaFold has largely solved the data availability issue, but the need for robust, model-based inference methods for structural data remained. This paper addresses this by adapting a "3Di" structural alphabet, originally developed for homology searching, into a character-based system for phylogenetic analysis.

Methods

The core of this work is the application of the Foldseek "3Di" alphabet. For each residue in a protein structure, Foldseek identifies its closest tertiary interaction neighbor and classifies this interaction into one of 20 discrete "3Di" states. These 3Di states are then treated as phylogenetic characters, analogous to amino acids. The authors performed extensive Maximum Likelihood (ML) phylogenetic analyses using IQtree, comparing various combinations of data sources (PDB structures, AlphaFold predictions), data types (amino acids, 3Di characters, or both), alignment methods (structure-free vs. structure-informed), and substitution models (including a custom 3Di-specific rate matrix). They also explored partitioning AA and 3Di data to allow for different evolutionary models.

Datasets

The primary dataset used is a collection of 53 PDB structures from the ferritin-like superfamily, previously used by Malik et al. (2020). For AlphaFold-predicted structures, the authors downloaded predictions corresponding to these PDB entries, ensuring high-quality predictions (mean pLDDT of 94.1%). The reference tree for comparison was the structural-distances NJ tree from Malik et al. (2020).

Key Insights and Ideas

  • 3Di characters as phylogenetic data: The paper demonstrates that 3Di states, derived from tertiary structure interactions, can be effectively used as discrete phylogenetic characters, similar to amino acids. This opens the door to integrating structural information into standard phylogenetic pipelines.
  • Bridging the twilight zone: By combining structural information (3Di) with amino acid sequences, the method shows improved accuracy in phylogenetic inference, particularly for distantly related proteins where sequence-based methods struggle.
  • Speed and accessibility: The proposed method drastically reduces computational time from weeks (for previous state-of-the-art structural methods) to minutes, making structural phylogenetics accessible on desktop computers.
  • AlphaFold's impact: The availability of accurate AlphaFold structures makes this structural phylogenetic approach broadly applicable, even for proteins without experimentally determined structures.

Key Results

  • Improved phylogenetic accuracy: Analyses combining amino acids and 3Di characters, with appropriate partitioning and custom models, produced phylogenies that most closely matched the reference structural distances tree from Malik et al. (2020).
  • Reduced long-branch attraction: Structure-free AA-only analyses exhibited long-branch attraction errors, which were mitigated by the inclusion of 3Di characters.
  • Significant speedup: Phylogenetic analyses that previously took weeks (e.g., MD-based bootstrapping) could be completed in minutes using the proposed ML approach.
  • PDB vs. AlphaFold equivalence: PDB structures and AlphaFold-predicted structures yielded equivalent phylogenetic results, highlighting the utility of predicted structures.
  • 3Di characters are more conserved: 3Di characters showed substantially higher conservation across sites compared to amino acids in the ferritin superfamily.

Limitations and Future Work

  • Sensitivity to perturbations: The authors acknowledge that it remains unclear how sensitive 3Di encoding is to small structural perturbations (e.g., indels, minor errors in structure prediction). However, evidence suggests 3Di characters are likely robust.
  • "Mixing and matching" structures: Caution is advised when combining structures from different sources (PDB, AlphaFold predictions, different conformations) as it could introduce systematic biases.
  • Site independence assumption: The definition of 3Di characters as descriptors of tertiary interactions between residue pairs might violate the assumption of site independence in likelihood calculations, potentially leading to inflated confidence measures.
  • Missing information: 3Di characters primarily capture backbone interactions and may miss information from side-chain changes or dihedral angles.
  • Future work: The authors suggest exploring optimized 3Di substitution matrices for different protein types/regions, developing Bayesian structural phylogenetics, and testing this approach on systems with known phylogenies to further validate its utility. They also highlight the potential for this method to revolutionize the study of deep evolutionary relationships, potentially addressing questions about the origin of protein families and fundamental cellular machinery.

Summary updated

Abstract

Abstract Protein structure is more conserved than protein sequence, and therefore may be useful for phylogenetic inference beyond the “twilight zone” where sequence similarity is highly decayed. Until recently, structural phylogenetics was constrained by the lack of solved structures for most proteins, and the reliance on phylogenetic distance methods which made it difficult to treat inference and uncertainty statistically. AlphaFold has mostly overcome the first problem by making structural predictions readily available. We address the second problem by redeploying a structural alphabet recently developed for Foldseek, a highly-efficient deep homology search program. For each residue in a structure, Foldseek identifies a tertiary interaction closest-neighbor residue in the structure, and classifies it into one of twenty “3Di” states. We test the hypothesis that 3Dis can be used as standard phylogenetic characters using a dataset of 53 structures from the ferritin-like superfamily. We performed 60 IQtree Maximum Likelihood runs to compare structure-free, PDB, and AlphaFold analyses, and default versus custom model sets that include a 3DI-specific rate matrix. Analyses that combine amino acids, 3Di characters, partitioning, and custom models produce the closest match to the structural distances tree of Malik et al. (2020), avoiding the long-branch attraction errors of structure-free analyses. Analyses include standard ultrafast bootstrapping confidence measures, and take minutes instead of weeks to run on desktop computers. These results suggest that structural phylogenetics could soon be routine practice in protein phylogenetics, allowing the re-exploration of many fundamental phylogenetic problems.
BibTeX
@misc{puentelelievre2023tertiary,
  author = {Caroline Puente-Lelièvre and Ashar J. Malik and Jordan Douglas and David B. Ascher and Matthew A. B. Baker and Jane R. Allison and Anthony M. Poole and Daniel Lundin and Matthew S. Fullmer and Remco Bouckert and Hyunbin Kim and Martin Steinegger and Nicholas J. Matzke},
  title = {{Tertiary-interaction characters enable fast, model-based structural phylogenetics beyond the twilight zone}},
  year = {2023},
  doi = {10.1101/2023.12.12.571181},
  howpublished = {bioRxiv},
}

Loading related content...

Figure