Towards Discovering Structural Signatures of Protein Folds Based on Logical Hidden Markov Models

Kristian Kersting, Tapani Raiko, Stefan Kramer, Luc De Raedt

Introduction

Understanding the relationship between protein structure and function is a cornerstone of modern bioinformatics. A central challenge in this field is the classification of 3D protein structures, or folds. While Hidden Markov Models (HMMs) have long been the standard for sequence analysis, they struggle with the hierarchical and structured nature of protein data. Traditional HMMs treat sequences as "flat" strings of unstructured symbols, failing to capture the inherent logic of protein architecture—such as the relationship between the length and orientation of secondary structures. To address these limitations, this paper introduces Logical Hidden Markov Models (LOHMMs), which integrate the probabilistic framework of HMMs with the representational power of first-order logic.

Logical Hidden Markov Models (LOHMMs)

LOHMMs extend traditional HMMs by replacing simple, atomic states with logical atoms, referred to as "abstract states." For example, an abstract state might be represented as $hc(X)$, where $X$ is a variable. This allows a single abstract state to represent an entire class of physical states, significantly reducing model complexity.

Key technical features of LOHMMs include:

  • Abstract Transitions: Transitions occur between logical atoms, allowing the model to generalize patterns across different specific instances.
  • Variable Binding and Unification: Variables can carry information (e.g., the length of a beta-strand) across transitions. This enables the model to "remember" properties without requiring a separate state for every possible value.
  • Default Reasoning: The models utilize different edge types (solid, dotted, and dashed) to represent standard transitions, identical behaviors across states, and exceptions to general rules.
A Logical Hidden Markov Model (LOHMM) illustrating abstract states and transitions with logical predicates.

The authors adapted the standard Expectation-Maximization (EM) algorithm, specifically the Baum-Welch approach, to train these models. This allows LOHMMs to learn transition and emission probabilities directly from structured protein data.

Experimental Evaluation

The proposed approach was evaluated using the Structural Classification of Proteins (SCOP) database (version 1.57). The study focused on five highly populated subclasses of alpha and beta proteins, including TIM beta/alpha-barrels and NAD(P)-binding Rossmann-folds. Data was extracted from the Protein Data Bank (PDB) and converted into sequences of logical atoms, such as $st(plus, 10)$, representing a parallel beta-strand of length 10.

Model Grounding and Inference

To perform inference, the LOHMM is "unrolled" into a grounded trellis. This process maps the abstract logical states to the specific values found in a protein sequence while maintaining the high-level logic defined in the model.

The grounded trellis induced by a LOHMM, showing the relationship between abstract states and observed protein sequences.

Key Results and Insights

  • Massive Model Compression: One of the most significant findings is the efficiency of LOHMMs. A LOHMM with only 74 transition parameters was found to represent the same complexity as a traditional HMM requiring over 62,000 parameters. This compression makes the models far more interpretable.
  • Classification Performance: The LOHMMs achieved an overall classification accuracy of 74% across the five folds. This performance is comparable to state-of-the-art Inductive Logic Programming (ILP) methods but offers the added advantage of a probabilistic framework.
  • Interpretable Signatures: Due to their compact nature, researchers can inspect the learned probability distributions to identify specific structural "signatures." For instance, the model could identify folds with a lower probability of containing right-handed alpha helices.
  • Computational Efficiency: Training was highly efficient, taking approximately 5 minutes per fold on standard hardware (Pentium-III 600 MHz), proving that logical overhead does not hinder practical application.

Conclusion and Future Work

LOHMMs provide a powerful tool for discovering structural signatures in proteins by combining logic and probability. While highly effective, the current model assumes independence between predicate arguments (e.g., orientation and length). Future research will focus on modeling these dependencies and developing methods for "logical structure learning" to automatically discover the rules and connections of the models from data, rather than designing them by hand.

Summary updated

Abstract

With the growing number of determined protein structures and the availability of classification schemes, it becomes increasingly important to develop computer methods that automatically extract structural signatures for classes of proteins. In this paper, we introduce and apply a new Machine Learning technique, Logical Hidden Markov Models (LOHMMs), to the task of finding structural signatures of folds according to the classification scheme SCOP. Our results indicate that LOHMMs are applicable to this task and possess several advantages over other approaches.
BibTeX
@inproceedings{kersting2003towards,
  author = {Kristian Kersting and Tapani Raiko and Stefan Kramer and Luc De Raedt},
  title = {{Towards Discovering Structural Signatures of Protein Folds Based on Logical Hidden Markov Models}},
  booktitle = {Pacific Symposium on Biocomputing},
  year = {2003},
  url = {https://openreview.net/forum?id=WRHFQRi-hl},
}
Figure