PMID- 25669327
OWN - NLM
STAT- MEDLINE
DCOM- 20160504
LR  - 20180810
IS  - 1757-6334 (Electronic)
IS  - 0219-7200 (Linking)
VI  - 13
IP  - 4
DP  - 2015 Aug
TI  - The study of unfoldable self-avoiding walks - Application to protein structure 
      prediction software.
PG  - 1550009
LID - 10.1142/S0219720015500092 [doi]
AB  - 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.
FAU - Guyeux, Christophe
AU  - Guyeux C
AD  - FEMTO-ST Institute, Universite de Franche-Comte/CNRS/ENSMM/UTBM, Besancon, 
      France.
FAU - Nicod, Jean-Marc
AU  - Nicod JM
AD  - FEMTO-ST Institute, Universite de Franche-Comte/CNRS/ENSMM/UTBM, Besancon, 
      France.
FAU - Philippe, Laurent
AU  - Philippe L
AD  - FEMTO-ST Institute, Universite de Franche-Comte/CNRS/ENSMM/UTBM, Besancon, 
      France.
FAU - Bahi, Jacques M
AU  - Bahi JM
AD  - FEMTO-ST Institute, Universite de Franche-Comte/CNRS/ENSMM/UTBM, Besancon, 
      France.
LA  - eng
PT  - Journal Article
PT  - Research Support, Non-U.S. Gov't
DEP - 20141223
PL  - Singapore
TA  - J Bioinform Comput Biol
JT  - Journal of bioinformatics and computational biology
JID - 101187344
RN  - 0 (Proteins)
SB  - IM
MH  - Algorithms
MH  - Computational Biology/methods
MH  - Protein Conformation
MH  - *Protein Folding
MH  - Proteins/*chemistry
MH  - *Software
OTO - NOTNLM
OT  - Protein structure prediction
OT  - combinatorics algorithms
OT  - discrete structures
OT  - problem complexity
OT  - protein folding
OT  - self-avoiding walks
EDAT- 2015/02/12 06:00
MHDA- 2016/05/05 06:00
CRDT- 2015/02/12 06:00
PHST- 2015/02/12 06:00 [entrez]
PHST- 2015/02/12 06:00 [pubmed]
PHST- 2016/05/05 06:00 [medline]
AID - 10.1142/S0219720015500092 [doi]
PST - ppublish
SO  - J Bioinform Comput Biol. 2015 Aug;13(4):1550009. doi: 10.1142/S0219720015500092. 
      Epub 2014 Dec 23.