Revealing divergent evolution, identifying circular permutations and detecting active-sites by protein structure comparison.

Luonan Chen, Ling‐Yun Wu, Yong Wang, Shihua Zhang, Xiang‐Sun ZhangBMC 2006 · DOI

TL;DR

This paper introduces SAMO, a novel software tool that aligns protein structures using a multi-objective optimization approach. Unlike previous methods, SAMO is sequence-order independent, allowing it to reveal evolutionary relationships, identify circularly permuted proteins, and pinpoint active sites with greater accuracy and efficiency.

What Problem Does This Paper Address?

Understanding the three-dimensional structure of proteins is crucial for deciphering their function and evolutionary history. Protein structure comparison is a fundamental task in computational biology, essential for tasks like predicting protein function, classifying protein families, and understanding evolutionary relationships. However, existing methods often rely on sequence order, which can miss similarities between proteins that have undergone significant structural rearrangements or have evolved through convergent evolution. This limitation hinders the ability to detect subtle evolutionary signals, identify proteins with rearranged sequences (circular permutations), and pinpoint functional regions like active sites, especially when these regions are not conserved in sequence.

Methods

The core of SAMO's innovation lies in its formulation of protein structure alignment as a multi-objective optimization problem. Specifically, it aims to simultaneously:

  • Maximize the number of aligned atoms: This ensures a comprehensive comparison.
  • Minimize the root mean square distance (RMSD) of aligned atoms: This ensures the aligned structures are geometrically similar.

This is achieved through a sequence-order independent strategy, meaning the algorithm doesn't assume a direct correspondence between amino acids in the same linear order. The problem is then decomposed into two subproblems:

  1. Weighted Least Square Subproblem (LSS): This subproblem finds the optimal rigid body transformation (translation and rotation) to align the protein structures, given a set of atom correspondences. It's solved efficiently using Singular Value Decomposition (SVD).
  2. Integer Linear Programming Subproblem (LPS): This subproblem determines the optimal set of atom correspondences (the alignment matrix) for the given transformation. It's tackled using a specialized bipartite matching algorithm, which is theoretically guaranteed to find an integer solution.

The algorithm iteratively solves LSS and LPS until convergence. An annealing process is incorporated to improve the quality of the solution by expanding the search space, especially when initial alignments are not satisfactory.

Datasets

The paper utilizes benchmark examples from the Protein Data Bank (PDB) and the SCOP database for numerical simulations. Specific examples include protein pairs from the "Reductases," "Globins," and "Ten difficult structures" categories, as well as examples for "Different folds," "Different Classes," and "Circular permutation." No new benchmark datasets were introduced.

Key Insights and Ideas

  • Sequence-order independence is key: By not being constrained by the linear sequence of amino acids, SAMO can uncover structural similarities that traditional methods miss, revealing deeper evolutionary connections and functional similarities.
  • Multi-objective optimization captures trade-offs: The explicit formulation of maximizing aligned atoms and minimizing RMSD acknowledges the inherent trade-off in structure alignment and allows for a more nuanced understanding of similarity.
  • Decomposition enables efficiency: Breaking down the complex optimization problem into LSS and LPS subproblems, and solving them iteratively, makes the algorithm computationally feasible for large proteins.
  • Detecting "real" 3D motifs: SAMO can identify structural motifs or active sites that are functionally important but may not be conserved in sequence, offering a new way to understand protein function.
  • Circular permutation detection is enhanced: The sequence-order independent nature of SAMO makes it particularly adept at finding circularly permuted proteins, which are challenging for sequence-based methods.

Key Results

  • Improved accuracy and efficiency: SAMO consistently outperforms existing methods (Dali, CE, Lund) in terms of RMSD and the number of aligned atoms across various benchmark datasets, especially for difficult-to-align protein pairs.
  • Fast computation: The algorithm is implemented in C++ and typically requires only a few minutes (often less than 10 seconds on a Pentium 4 CPU) for structure alignment, making it practical for large-scale analyses.
  • Successful detection of evolutionary divergence: SAMO effectively identifies similarities between divergently evolved proteins, often with lower RMSD and more matched pairs than conventional methods.
  • Identification of circular permutations: The method demonstrates a significant advantage in detecting circularly permuted proteins, often finding double the number of matched amino-acid pairs compared to other methods.
  • Detection of active sites: SAMO successfully identifies structural motifs and active sites, even when they are not conserved in sequence, providing valuable insights into protein function.

Limitations and Future Work

  • Global optimality: The authors acknowledge that while SAMO finds optimal solutions for a given parameter, the protein structure alignment problem is non-convex, meaning the algorithm may not always find the globally optimal solution and can be sensitive to initial conditions. The annealing process helps mitigate this.
  • Interpretation of matches: While SAMO identifies structural motifs, manual inspection may still be needed to confirm their biological significance, especially for cases where aligned residues are distributed widely or do not form contiguous local regions.
  • Future work: The paper suggests that SAMO's ability to detect order-independent surface patterns can be applied to assess similarity of protein pockets, and that the tool can be integrated into larger applications like protein folding prediction and computer-aided drug design. The authors also envision providing SAMO as a web service for routine comparisons against large databases.

Summary updated

Abstract

A novel formulation is proposed to accurately align protein structures in the framework of multi-objective optimization, based on a sequence order-independent strategy. A fast and accurate algorithm based on the bipartite matching algorithm is developed by exploiting the special features. Convergence of computation is shown in experiments and is also theoretically proven.
BibTeX
@inproceedings{chen2006revealing,
  author = {Luonan Chen and Ling‐Yun Wu and Yong Wang and Shihua Zhang and Xiang‐Sun Zhang},
  title = {{Revealing divergent evolution, identifying circular permutations and detecting active-sites by protein structure comparison.}},
  booktitle = {BMC},
  year = {2006},
  doi = {10.1186/1472-6807-6-18},
}
Figure