A Novel Framework for Ab Initio Coarse Protein Structure Prediction

Area of Science:

• Computational Biology
• Bioinformatics
• Protein Structure Prediction

Background:

• The Protein Structure Prediction (PSP) problem, even with the simplified Hydrophobic-Polar (HP) model, remains computationally challenging (NP-complete).
• Efficient exploration of the vast search space is crucial for obtaining accurate protein conformations.

Purpose of the Study:

• To develop a systematic and problem-specific evolutionary algorithm hybridized with local search for efficient PSP.
• To enhance the accuracy and speed of protein structure prediction using novel algorithmic components.

Main Methods:

• A novel two-tier evolutionary framework integrating hill climbing local search.
• Implementation of a new initialization method for valid, high-fitness individuals.
• Utilization of probability-based selection operators to prevent local convergence.
• Inclusion of a secondary structure-based mutation operator for improved structural accuracy.

Main Results:

• The developed framework demonstrated superior performance in accuracy (fitness value) and speed (convergence rate) compared to state-of-the-art algorithms.
• Validation on benchmark and real-world protein sequences from databases confirmed the framework's effectiveness.
• The proposed methods were tested on both square and triangular lattices.

Conclusions:

• The novel evolutionary approach significantly improves protein structure prediction efficiency and accuracy.
• The generic concepts enhancing performance can be adapted to other population-based search algorithms.
• This work provides a robust framework for tackling the PSP problem in computational biology.