On the complexity of string folding (Q5961626)

A fold of a finite string \(S\) over a given alphabet is an embedding of \(S\) in some fixed infinite grid, such as the square or cubic mesh. The score of a fold is the number of pairs of matching string symbols which are embedded at adjacent grid vertices. Folds of strings in two- and three-dimensional meshes are considered, and the corresponding problems of optimizing the score or achieving a given target score are shown to be NP-hard. The motivation for the string-folding problems considered here lies in computational biology. Prediction of the three-dimensional structure of a protein from its known linear sequence of amino acids is an important practical open problem, which seems to be extremely challenging. The way in which a protein folds determines many of its biological and chemical properties. A natural approach is to look for a spatial configuration achieving a minimum free energy level. The energy is determined by such factors as the number of chemical bonds established between amino acid residues in the sequence and the number of hydrophobic interactions.