The study of unfoldable self-avoiding walks - Application to protein structure prediction software.
Fiche publication
Date publication
août 2015
Journal
Journal of bioinformatics and computational biology
Auteurs
Membres identifiés du Cancéropôle Est :
Pr PHILIPPE Laurent
Tous les auteurs :
Guyeux C, Nicod JM, Philippe L, Bahi JM
Lien Pubmed
Résumé
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.
Mots clés
Protein structure prediction, combinatorics algorithms, discrete structures, problem complexity, protein folding, self-avoiding walks
Référence
J Bioinform Comput Biol. 2015 Aug;13(4):1550009