dorsal/arxiv
View SchemaProtein structure prediction as a hard optimization problem: the genetic algorithm approach
| Authors | Mehul M. Khimasia, Peter V. Coveney |
|---|---|
| Categories | |
| ArXiv ID | physics/9708012 |
| URL | https://arxiv.org/abs/physics/9708012 |
Abstract
Protein structure prediction can be shown to be an NP-hard problem; the number of conformations grows exponentially with the number of residues. The native conformations of proteins occupy a very small subset of these, hence an exploratory, robust search algorithm, such as a genetic algorithm (GA), is required. The dynamics of GAs tend to be complicated and problem-specific. However, their empirical success warrants their further study. In this paper, guidelines for the design of genetic algorithms for protein structure prediction are determined. To accomplish this, the performance of the simplest genetic algorithm is investigated for simple lattice-based protein structure prediction models (which is extendible to real-space), using energy minimization. The study has led us to two important conclusions for `protein-structure-prediction-genetic-algorithms'. Firstly, they require high resolution building blocks attainable by multi-point crossovers and secondly they require a local dynamics operator to `fine tune' good conformations. Furthermore, we introduce a statistical mechanical approach to analyse the genetic algorithm dynamics and suggest a convergence criterion using a quantity analogous to the free energy of population.
{
"annotation_id": "c98e97dc-01f3-4bef-ad22-548cf769221e",
"date_created": "2026-03-02T18:01:20.994000Z",
"date_modified": "2026-03-02T18:01:20.994000Z",
"file_hash": "35b159b6ce0e3002db75c9169be397822259d773176322d51ca2a4834adca38f",
"private": false,
"record": {
"abstract": "Protein structure prediction can be shown to be an NP-hard problem; the\nnumber of conformations grows exponentially with the number of residues. The\nnative conformations of proteins occupy a very small subset of these, hence an\nexploratory, robust search algorithm, such as a genetic algorithm (GA), is\nrequired. The dynamics of GAs tend to be complicated and problem-specific.\nHowever, their empirical success warrants their further study. In this paper,\nguidelines for the design of genetic algorithms for protein structure\nprediction are determined. To accomplish this, the performance of the simplest\ngenetic algorithm is investigated for simple lattice-based protein structure\nprediction models (which is extendible to real-space), using energy\nminimization. The study has led us to two important conclusions for\n`protein-structure-prediction-genetic-algorithms\u0027. Firstly, they require high\nresolution building blocks attainable by multi-point crossovers and secondly\nthey require a local dynamics operator to `fine tune\u0027 good conformations.\nFurthermore, we introduce a statistical mechanical approach to analyse the\ngenetic algorithm dynamics and suggest a convergence criterion using a quantity\nanalogous to the free energy of population.",
"arxiv_id": "physics/9708012",
"authors": [
"Mehul M. Khimasia",
"Peter V. Coveney"
],
"categories": [
"physics.chem-ph"
],
"title": "Protein structure prediction as a hard optimization problem: the genetic algorithm approach",
"url": "https://arxiv.org/abs/physics/9708012"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "59fd1902-fbe0-49a6-88ea-dd96ebd7ef28",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}