title: The study of unfoldable self-avoiding walks - Application to protein structure prediction software.
abstract: Self-avoiding walks (SAWs) are the source of very difficult problems in probability and enumerative combinatorics. They are of great interest as, for example, they are the basis of protein structure prediction (PSP) in bioinformatics. The authors of this paper have previously shown that, depending on the prediction algorithm, the sets of obtained walk conformations differ: For example, all the SAWs can be generated using stretching-based algorithms whereas only the unfoldable SAWs can be obtained with methods that iteratively fold the straight line. A deeper study of (non-)unfoldable SAWs is presented in this paper. The contribution is first a survey of what is currently known about these sets. In particular, we provide clear definitions of various subsets of SAWs related to pivot moves (unfoldable and non-unfoldable SAWs, etc.) and the first results that we have obtained, theoretically or computationally, on these sets. Then a new theorem on the number of non-unfoldable SAWs is demonstrated. Finally, a list of open questions is provided and the consequences on the PSP problem is proposed.
authors: FEMTO-ST Institute, Université de Franche-Comté/CNRS/ENSMM/UTBM, Besançon, France.
authors: Christophe
authors: C
authors: Guyeux
authors: FEMTO-ST Institute, Université de Franche-Comté/CNRS/ENSMM/UTBM, Besançon, France.
authors: Jean-Marc
authors: JM
authors: Nicod
authors: FEMTO-ST Institute, Université de Franche-Comté/CNRS/ENSMM/UTBM, Besançon, France.
authors: Laurent
authors: L
authors: Philippe
authors: FEMTO-ST Institute, Université de Franche-Comté/CNRS/ENSMM/UTBM, Besançon, France.
authors: Jacques M
authors: JM
authors: Bahi
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D011487:Protein Conformation; D017510:Protein Folding; D011506:Proteins / Q000737:chemistry*; D012984:Software
chemical_list: D011506:Proteins
keywords: Protein structure prediction; combinatorics algorithms; discrete structures; problem complexity; protein folding; self-avoiding walks