Can HP-protein Folding Be Solved with Genetic Algorithms? Maybe not

Reitze Jansen; Ruben Horn; Okke van Eck; Kristian Verduin; Sarah L. Thomson; Daan van den Berg

doi:10.5220/0012248500003595

Can HP-protein Folding Be Solved with Genetic Algorithms? Maybe not

Reitze Jansen, Ruben Horn, Okke van Eck, Kristian Verduin, Sarah L. Thomson, Daan van den Berg

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Genetic algorithms might not be able to solve the HP-protein folding problem because creating random individuals for an initial population is very hard, if not impossible. The reason for this, is that the expected number of constraint violations increases with instance size when randomly sampling individuals, as we will show in an experiment. Thereby, the probability of randomly sampling a valid individual decreases exponentially with instance size. This immediately prohibits resampling, and repair mechanisms might also be non-applicable. Backtracking could generate a valid random individual, but it runs in exponential time, and is therefore also unsuitable. No wonder that previous approaches do not report how (often) random samples are created, and only address small instances. We contrast our findings with TSP, which is also NP-hard, but does not have these problems.

Original language	English
Title of host publication	Proceedings of the 15th International Joint Conference on Computational Intelligence ECTA
Subtitle of host publication	Volume 1
Editors	Niki van Stein, Francesco Marcelloni, H. K. Lam, Marie Cottrell, Joaquim Filipe
Publisher	Science and Technology Publications, Lda
Pages	131-140
Number of pages	10
Volume	1
ISBN (Electronic)	9789897586743
DOIs	https://doi.org/10.5220/0012248500003595
Publication status	Published - 2023
Event	15th International Joint Conference on Computational Intelligence, IJCCI 2023 - Hybrid, Rome, Italy Duration: 13 Nov 2023 → 15 Nov 2023

Publication series

Name	International Joint Conference on Computational Intelligence
ISSN (Electronic)	2184-3236

Conference

Conference	15th International Joint Conference on Computational Intelligence, IJCCI 2023
Country/Territory	Italy
City	Hybrid, Rome
Period	13/11/23 → 15/11/23

Bibliographical note

Publisher Copyright:
© 2023 by SCITEPRESS – Science and Technology Publications, Lda.

Keywords

Constraint Hierarchy
Constraints
Evolutionary Computing
Genetic Algorithms
Protein Folding

Access to Document

10.5220/0012248500003595

Persistent URL (handle)

Copy link address

Cite this

Jansen, R., Horn, R., van Eck, O., Verduin, K., Thomson, S. L., & van den Berg, D. (2023). Can HP-protein Folding Be Solved with Genetic Algorithms? Maybe not. In N. van Stein, F. Marcelloni, H. K. Lam, M. Cottrell, & J. Filipe (Eds.), Proceedings of the 15th International Joint Conference on Computational Intelligence ECTA: Volume 1 (Vol. 1, pp. 131-140). (International Joint Conference on Computational Intelligence). Science and Technology Publications, Lda. https://doi.org/10.5220/0012248500003595

Jansen, Reitze ; Horn, Ruben ; van Eck, Okke et al. / Can HP-protein Folding Be Solved with Genetic Algorithms? Maybe not. Proceedings of the 15th International Joint Conference on Computational Intelligence ECTA: Volume 1. editor / Niki van Stein ; Francesco Marcelloni ; H. K. Lam ; Marie Cottrell ; Joaquim Filipe. Vol. 1 Science and Technology Publications, Lda, 2023. pp. 131-140 (International Joint Conference on Computational Intelligence).

@inproceedings{5a8d7aaa31234b2cade2806ffc35356e,

title = "Can HP-protein Folding Be Solved with Genetic Algorithms? Maybe not",

abstract = "Genetic algorithms might not be able to solve the HP-protein folding problem because creating random individuals for an initial population is very hard, if not impossible. The reason for this, is that the expected number of constraint violations increases with instance size when randomly sampling individuals, as we will show in an experiment. Thereby, the probability of randomly sampling a valid individual decreases exponentially with instance size. This immediately prohibits resampling, and repair mechanisms might also be non-applicable. Backtracking could generate a valid random individual, but it runs in exponential time, and is therefore also unsuitable. No wonder that previous approaches do not report how (often) random samples are created, and only address small instances. We contrast our findings with TSP, which is also NP-hard, but does not have these problems.",

keywords = "Constraint Hierarchy, Constraints, Evolutionary Computing, Genetic Algorithms, Protein Folding",

author = "Reitze Jansen and Ruben Horn and {van Eck}, Okke and Kristian Verduin and Thomson, {Sarah L.} and {van den Berg}, Daan",

note = "Publisher Copyright: {\textcopyright} 2023 by SCITEPRESS – Science and Technology Publications, Lda.; 15th International Joint Conference on Computational Intelligence, IJCCI 2023 ; Conference date: 13-11-2023 Through 15-11-2023",

year = "2023",

doi = "10.5220/0012248500003595",

language = "English",

volume = "1",

series = "International Joint Conference on Computational Intelligence",

publisher = "Science and Technology Publications, Lda",

pages = "131--140",

editor = "{van Stein}, Niki and Francesco Marcelloni and Lam, {H. K.} and Marie Cottrell and Joaquim Filipe",

booktitle = "Proceedings of the 15th International Joint Conference on Computational Intelligence ECTA",

}

Jansen, R, Horn, R, van Eck, O, Verduin, K, Thomson, SL & van den Berg, D 2023, Can HP-protein Folding Be Solved with Genetic Algorithms? Maybe not. in N van Stein, F Marcelloni, HK Lam, M Cottrell & J Filipe (eds), Proceedings of the 15th International Joint Conference on Computational Intelligence ECTA: Volume 1. vol. 1, International Joint Conference on Computational Intelligence, Science and Technology Publications, Lda, pp. 131-140, 15th International Joint Conference on Computational Intelligence, IJCCI 2023, Hybrid, Rome, Italy, 13/11/23. https://doi.org/10.5220/0012248500003595

Can HP-protein Folding Be Solved with Genetic Algorithms? Maybe not. / Jansen, Reitze; Horn, Ruben; van Eck, Okke et al.
Proceedings of the 15th International Joint Conference on Computational Intelligence ECTA: Volume 1. ed. / Niki van Stein; Francesco Marcelloni; H. K. Lam; Marie Cottrell; Joaquim Filipe. Vol. 1 Science and Technology Publications, Lda, 2023. p. 131-140 (International Joint Conference on Computational Intelligence).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Can HP-protein Folding Be Solved with Genetic Algorithms? Maybe not

AU - Jansen, Reitze

AU - Horn, Ruben

AU - van Eck, Okke

AU - Verduin, Kristian

AU - Thomson, Sarah L.

AU - van den Berg, Daan

PY - 2023

Y1 - 2023

N2 - Genetic algorithms might not be able to solve the HP-protein folding problem because creating random individuals for an initial population is very hard, if not impossible. The reason for this, is that the expected number of constraint violations increases with instance size when randomly sampling individuals, as we will show in an experiment. Thereby, the probability of randomly sampling a valid individual decreases exponentially with instance size. This immediately prohibits resampling, and repair mechanisms might also be non-applicable. Backtracking could generate a valid random individual, but it runs in exponential time, and is therefore also unsuitable. No wonder that previous approaches do not report how (often) random samples are created, and only address small instances. We contrast our findings with TSP, which is also NP-hard, but does not have these problems.

AB - Genetic algorithms might not be able to solve the HP-protein folding problem because creating random individuals for an initial population is very hard, if not impossible. The reason for this, is that the expected number of constraint violations increases with instance size when randomly sampling individuals, as we will show in an experiment. Thereby, the probability of randomly sampling a valid individual decreases exponentially with instance size. This immediately prohibits resampling, and repair mechanisms might also be non-applicable. Backtracking could generate a valid random individual, but it runs in exponential time, and is therefore also unsuitable. No wonder that previous approaches do not report how (often) random samples are created, and only address small instances. We contrast our findings with TSP, which is also NP-hard, but does not have these problems.

KW - Constraint Hierarchy

KW - Constraints

KW - Evolutionary Computing

KW - Genetic Algorithms

KW - Protein Folding

UR - http://www.scopus.com/inward/record.url?scp=85188246644&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85188246644&partnerID=8YFLogxK

UR - https://www.scitepress.org/ProceedingsDetails.aspx?ID=z5f/p31NVmI=&t=1

U2 - 10.5220/0012248500003595

DO - 10.5220/0012248500003595

M3 - Conference contribution

AN - SCOPUS:85188246644

VL - 1

T3 - International Joint Conference on Computational Intelligence

SP - 131

EP - 140

BT - Proceedings of the 15th International Joint Conference on Computational Intelligence ECTA

A2 - van Stein, Niki

A2 - Marcelloni, Francesco

A2 - Lam, H. K.

A2 - Cottrell, Marie

A2 - Filipe, Joaquim

PB - Science and Technology Publications, Lda

T2 - 15th International Joint Conference on Computational Intelligence, IJCCI 2023

Y2 - 13 November 2023 through 15 November 2023

ER -

Jansen R, Horn R, van Eck O, Verduin K, Thomson SL, van den Berg D. Can HP-protein Folding Be Solved with Genetic Algorithms? Maybe not. In van Stein N, Marcelloni F, Lam HK, Cottrell M, Filipe J, editors, Proceedings of the 15th International Joint Conference on Computational Intelligence ECTA: Volume 1. Vol. 1. Science and Technology Publications, Lda. 2023. p. 131-140. (International Joint Conference on Computational Intelligence). doi: 10.5220/0012248500003595

Can HP-protein Folding Be Solved with Genetic Algorithms? Maybe not

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this