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.
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: 26 Aug 2020 *