TL;DR
This paper introduces a novel Self-Organizing Map (SOM) algorithm for predicting protein folding configurations using the simplified Hydrophobic-Polar (HP) model. Unlike previous methods that confined proteins to fixed-size lattices, this new approach allows proteins to self-organize into more flexible, non-rectangular shapes within larger lattices, potentially leading to more biologically relevant and stable structures.
What Problem Does This Paper Address?
Predicting the three-dimensional structure (tertiary structure) of a protein from its amino acid sequence (primary structure) is a fundamental challenge in bioinformatics. Experimentally determining protein structures is time-consuming and difficult. Computational methods aim to predict these structures, and a simplified model, the HP model, is widely used. In this model, amino acids are classified as either hydrophobic (H) or polar (P), and the goal is to find a configuration that maximizes the number of favorable H-H contacts, leading to a compact structure where hydrophobic residues are buried and polar residues are on the surface.
Traditional HP model studies often restrict protein folding to a fixed-size 2D lattice (e.g., an m x n grid), which forces the protein into a compact, often rectangular shape. This limitation can prevent the discovery of truly optimal or more biologically plausible structures, especially for sequences that don't naturally form such shapes. The problem is also computationally challenging, being NP-complete even in 2D. This paper addresses the need for a more flexible and general approach to protein folding prediction within the HP model, moving beyond the constraints of fixed, compact lattice structures.
Methods
The core of this paper is a new Self-Organizing Map (SOM) algorithm designed to overcome the limitations of previous HP model folding methods. The key innovations include:
- Flexible Lattice Size: Instead of using a lattice with the same number of points as amino acids (l = m x n), the proposed method uses a larger lattice (l > l') where the protein sequence can self-organize more freely. This allows for non-rectangular and more flexible configurations.
- Handling Unsymmetric Input/Output Spaces: The algorithm is adapted to handle the mismatch between the input sequence length and the larger lattice size.
- Modified SOM Training:
- Two-Part Training: The training phase is simplified into two parts. The first part uses a classical TSP update rule to maintain the sequence's bond connections. The second part introduces "remote forces" to simulate the hydrophobic interactions between amino acids, controlled by parameters (λ, μ, ν) for H-H, H-P, and P-P pairs.
- Set Partition Strategy: To manage the larger lattice, the learning sample set (lattice points) is partitioned into groups, allowing each amino acid to select a trainer. A deterministic annealing procedure is used to focus the training.
- Reduction Strategy of Learning Sample Set: To prevent over-learning and instability caused by boundary lattice points, the size of the learning sample set is gradually reduced during training.
- Local Search Procedure: A local search method is employed to address the "multi-mapping problem" (where multiple lattice points map to the same amino acid), which is a common issue in SOMs, especially with larger lattices. This helps ensure valid protein conformations.
Datasets
The paper uses several benchmark examples for evaluation:
- Yanikoglu and Erman's sequences: Used to compare with previous SOM-based folding results.
- HP benchmark sequences: A collection of sequences for the 2D HP model.
- Generated sequences: To test specific aspects of the algorithm, such as handling arbitrary lengths.
The paper notes that the benchmark examples include sequences up to 36 amino acids. The authors also refer to a dataset of designable structures for sequences of lengths 16-25 from a previous study (Irbäck et al.) for designability comparisons.
Key Insights and Ideas
- Flexibility is Key: Allowing proteins to fold into non-rectangular shapes within a larger lattice is crucial for finding more optimal and potentially biologically relevant structures. The rigid, compact lattice constraint can be a significant impediment.
- Designability Matters: The concept of "designability" (how many sequences can fold into a specific structure) is highlighted as a critical metric for evaluating protein structures, beyond just energy minimization. Highly designable structures are more likely to be stable and "protein-like."
- Non-Rectangular Structures are More Designable: The numerical results strongly suggest that non-rectangular protein structures generally exhibit higher designability than their rectangular counterparts. This reinforces the idea that the proposed flexible folding approach is more likely to discover important structural motifs.
- SOM Adaptation is Powerful: Adapting the SOM algorithm with new training strategies and a local search mechanism effectively tackles the challenges posed by larger, more flexible folding spaces.
Key Results
- The proposed SOM algorithm successfully finds optimal or near-optimal configurations for several HP benchmark examples, including sequences up to 36 amino acids.
- The algorithm demonstrates the ability to handle arbitrary protein lengths and generate non-rectangular structures, which are often missed by conventional methods.
- Numerical simulations comparing designability show that non-rectangular structures, discoverable by this new method, generally have significantly higher designability than rectangular structures. For example, for sequences of length 25, only a small fraction (0.17%) of designable structures are rectangular.
- The running time of the new SOM method increases linearly with the chain length, similar to previous SOM approaches.
Limitations and Future Work
- Convergence Issues: The paper acknowledges that the algorithm can suffer from convergence problems, particularly when the lattice size is significantly larger than the sequence length.
- Computational Cost: While efficient for small sequences, the algorithm can still be time-consuming for very large-scale folding problems.
- Sub-optimal Solutions: For large input spaces, sub-optimal solutions may be obtained, which might not be the absolute minimum energy configurations.
- Future Research Directions:
- Improving the learning strategies to enhance convergence and reduce computational time.
- Exploring combinations with other algorithms or incorporating biological insights for better initial values.
- Investigating lattice models with larger alphabet sizes for increased prediction accuracy.
- Further studying the effectiveness of the SOM algorithm for larger protein sequences.
Summary updated