NK Landscape; Genetic Algorithm; Benchmark function
Résumé :
[en] This paper introduces two new nominal NK Landscape model instances designed to mimic the properties of one challenging optimisation problem from biology: the Inverse Folding Problem (IFP), here focusing on a simpler secondary structure version. Through landscape analysis tests, numerous problem properties are identified and used to parameterise and validate model instances in terms of epistatic links, adaptive- and random walk characteristics. Then the performance of different Genetic Algorithms (GAs) is compared on both the new NK Models and the original IFP, in terms of population diversity, solution quality and convergence characteristics. It is demonstrated that very similar properties are captured in all presented tests with a significantly faster evaluation time compared to the real IFP. The future purpose of such a model is to provide a generic benchmark for algorithms targeting protein sequence optimisation, specifically in protein design. It may also provide the foundation for more in-depth studies of the size, shape and characteristics of the solution space of good solutions to the IFP.
Centre de recherche :
ULHPC - University of Luxembourg: High Performance Computing
Disciplines :
Sciences informatiques
Auteur, co-auteur :
NIELSEN, Sune Steinbjorn ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
DANOY, Grégoire ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
BOUVRY, Pascal ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Talbi, El-Ghazali
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
NK Landscape Instances Mimicking the Protein Inverse Folding Problem Towards Future Benchmarks
Date de publication/diffusion :
2015
Nom de la manifestation :
The Genetic and Evolutionary Computation Conference (GECCO 2015)
Lieu de la manifestation :
Madrid, Espagne
Date de la manifestation :
from 11-07-2015 to 12-07-2015
Manifestation à portée :
International
Titre de l'ouvrage principal :
GECCO Companion '15 Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation
S. A. Kauffman. The origins of order: Self-organization and selection in evolution. Oxford university press, 1993.
S. A. Kauffman and E. D. Weinberger. The nk model of rugged fitness landscapes and its application to maturation of the immune response. Journal of theoretical biology, 141(2):211-245, 1989.
R. Li, M. T. Emmerich, J. Eggermont, E. G. Bovenkamp, T. Bäck, J. Dijkstra, and J. H. Reiber. Mixed-integer nk landscapes. In Parallel Problem Solving from Nature-PPSN IX, pages 42-51. Springer, 2006.
S. S. Nielsen, G. Danoy, W. Jurkowski, J. L. J. Laredo, R. Schneider, E.-G. Talbi, and P. Bouvry. A novel multi-objectivisation approach for optimising the protein inverse folding problem. In Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, page (To appear). Springer, 2015.
B. Rost and C. Sander. Combining evolutionary information and neural networks to predict protein secondary structure. Proteins, 19(1):55-72, May 1994.
S. Varrette, P. Bouvry, H. Cartiaux, and F. Georgatos. Management of an academic hpc cluster: The ul experience. In Proc. of the 2014 Intl. Conf. on High Performance Computing & Simulation (HPCS 2014), Bologna, Italy, July 2014. IEEE.
F. Wilcoxon. Individual comparisons by ranking methods. Biometrics Bulletin, 1(6):80-83, 1945.
