Towards comprehensive structural motif mining for better fold annotation in the "twilight zone" of sequence dissimilarity

Yi Jia, Jun Huan, Vincent Buhr, Jintao Zhang, Leonidas N. CarayannopoulosBMC Bioinformatics 2009 · DOI

TL;DR

This paper introduces APGM, a novel graph mining algorithm that identifies structural patterns in proteins, even when their sequences are highly dissimilar (the "twilight zone"). By representing protein structures as graphs and using approximate matching with compatibility matrices, APGM can discover meaningful motifs that are missed by traditional methods, leading to improved protein classification.

What Problem Does This Paper Address?

Identifying the function and structure of proteins is crucial, but it becomes challenging when comparing proteins with very similar structures but significantly different amino acid sequences. This "twilight zone" of sequence dissimilarity makes traditional sequence-based annotation methods unreliable. Existing structure-based methods often struggle with the inherent variability in protein structures due to mutations and measurement imprecision. The authors aim to develop a method that can robustly identify common structural patterns (motifs) across diverse protein structures, even with geometric distortions and amino acid variations, to improve protein fold annotation and classification.

Methods

The core of the paper is the APGM (Approximate Graph Mining) algorithm. Here's a breakdown of their approach:

  • Graph Representation: Protein structures are converted into geometric graphs. Amino acid residues are represented as nodes, and physical or chemical interactions between residues are represented as edges.
  • Almost-Delaunay Graph: To handle imprecision in protein structure coordinates, they use an "Almost-Delaunay" tessellation to define edges, which captures nearest neighbor relationships more robustly.
  • Approximate Subgraph Isomorphism: Unlike exact matching, APGM uses approximate subgraph isomorphism. This allows for "fuzzy" matching of structural patterns, tolerating geometric distortions and amino acid mismatches.
  • Compatibility Matrices: A key innovation is the use of compatibility matrices (like substitution matrices such as BLOSUM62) to quantify the probability of one amino acid residue being substituted for another. This provides a probabilistic framework for approximate matching.
  • Frequent Subgraph Mining: APGM iteratively builds larger patterns from smaller ones, identifying "frequent" approximate subgraphs that appear in a significant portion of the protein dataset, based on a support threshold.

Datasets

The authors evaluated their method using two sets of immunologically relevant protein domain families:

  • Immunoglobulin C1 Set: Consisting of 1786 proteins with an average length of 210 amino acids.
  • Immunoglobulin V Set: Consisting of 371 proteins with an average length of 194 amino acids.

These datasets were culled from the SCOP release 1.69 to ensure maximal pairwise sequence identity below specific thresholds (40% for C1, 30% for V). They also used a negative sample set of random proteins from the PDB for testing.

Key Insights and Ideas

  • Bridging the Sequence-Structure Gap: APGM effectively bridges the gap between sequence and structure by leveraging structural information to overcome the limitations of sequence-based methods in the "twilight zone."
  • Robustness to Variation: The use of approximate matching and compatibility matrices makes the method resilient to the natural variations and imprecisions found in protein structures.
  • "Structure Fingerprints": The identified frequent subgraph patterns can be viewed as "structure fingerprints" that are characteristic of protein families, even when sequence homology is low.
  • Beyond Exact Matching: The paper highlights that exact graph matching is insufficient for biological data where variations are common, and approximate matching is essential for discovering biologically relevant patterns.

Key Results

  • Improved Classification Accuracy: APGM-based feature extraction led to significantly higher classification accuracies compared to exact graph mining methods (MGM). For the Immunoglobulin C1 set, APGM achieved accuracies between 69% and 91%, while MGM was around 73%. For the Immunoglobulin V set, where exact matching failed, APGM achieved around 78% accuracy.
  • Discovery of Meaningful Patterns: APGM identified patterns that were not discovered by exact graph mining, suggesting it can find more subtle but biologically relevant structural motifs. For instance, it identified residues in contact with a ligand that were missed by exact methods.
  • Computational Performance: While approximate matching can be computationally intensive, APGM demonstrated reasonable performance, with its "pattern discovery rate" (patterns per unit time) being comparable to or better than exact methods, especially when considering the trade-off between pattern quality and computational cost.

Limitations and Future Work

  • Parameter Sensitivity: The authors note that the number of identified patterns can be influenced by the support threshold (σ), though it's less sensitive to the isomorphism threshold (τ). Careful selection of these parameters is important.
  • Generalizability: While the method was tested on immunoglobulin families, the authors suggest that its applicability can be extended to other protein families and domains where subgraph labels might have uncertainty (e.g., social networks).
  • Further Biological Validation: The authors acknowledge that while their findings are promising, comprehensive experimental studies involving multiple protein families are needed to draw more convincing conclusions about the biological significance of the mined patterns. They also suggest exploring the spatial distribution of residues within motifs for deeper biological insights.

Summary updated

BibTeX
@article{jia2009towards,
  author = {Yi Jia and Jun Huan and Vincent Buhr and Jintao Zhang and Leonidas N. Carayannopoulos},
  title = {{Towards comprehensive structural motif mining for better fold annotation in the "twilight zone" of sequence dissimilarity}},
  journal = {BMC Bioinformatics},
  year = {2009},
  doi = {10.1186/1471-2105-10-s1-s46},
}
Figure