Prediction of permuted super-secondary structures in β-barrel proteins

Computational structure prediction methods based on learning are poorly tractable for transmembrane β-barrel (TMB) proteins, for it is difficult to observe them with standard experimental techniques. Generally, those structures are not only a series of β-strands where each is bonded to the preceding and succeeding ones in the primary sequence, but they may contain Greek key or Jelly roll motifs as well. This may be described as a permutation on the order of the bonded segments. We model the protein folding problem with minimum energy into the search of the longest closed path in a weighted graph with respect to a given permutation. With dynamic programming, the algorithm runs in O(N²) for an identity permutation, and at most O(N⁴) for the Greek key motifs, where N is the number of amino acids. The prediction accuracy as well as the discrimination ability is favorably comparable with existing works.