Title: Advances in the enumeration of foldable self-avoiding walks

Authors: Christophe Guyeux; Jean-Claude Charr; Jacques Bou Abdo; Jacques Demerjian

Addresses: Femto-ST Institute, UMR 6174 CNRS, Université de Bourgogne Franche-Comté, France ' Femto-ST Institute, UMR 6174 CNRS, Université de Bourgogne Franche-Comté, France ' Faculty of Natural and Applied Sciences, Notre Dame University, P.O. Box 72, Deir El Kamar, Lebanon ' LARIFA-EDST, Faculty of Sciences, Lebanese University, 90656 Fanar, Lebanon

Abstract: Self-avoiding walks (SAWs) have been studied for a long time due to their intrinsic importance and the many application fields in which they operate. A new subset of SAWs, called foldable SAWs, has recently been discovered when investigating two different SAW manipulations embedded within existing protein structure prediction (PSP) software. Since then, several attempts have been made to find out more about these walks, including counting them. However, calculating the number of foldable SAWs appeared as a tough work, and current supercomputers fail to count foldable SAWs of length exceeding ≈ 30 steps. In this article, we present new progress in this enumeration, both theoretical (mathematics) and practical (computer science). A lower bound for the number of foldable SAWs is firstly proposed, by studying a special subset called prudent SAWs that is better known. The triangular and hexagonal lattices are then investigated for the first time, leading to new results about the enumeration of foldable SAWs on such lattices. Finally, a parallel genetic algorithm has been designed to discover new non-foldable SAWs of lengths ≈ 100 steps, and the results obtained with this algorithm are promising.

Keywords: self-avoiding walks; foldable SAWs; prudent SAWs; genetic algorithm.

DOI: 10.1504/IJCSE.2020.109398

International Journal of Computational Science and Engineering, 2020 Vol.22 No.4, pp.365 - 375

Received: 13 Nov 2018
Accepted: 05 Aug 2019

Published online: 08 Sep 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article