On the complexity of string folding

DOI10.1016/S0166-218X(96)00065-0MaRDI QIDQ5961626zbMATH OpenOpenAlexFDO

Authors Mike Paterson, Teresa Przytycka

Publication date 25 February 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Applications of graph theory (05C90) Complexity and performance of numerical algorithms (65Y20) Computational methods for problems pertaining to biology (92-08) Biochemistry, molecular biology (92C40)

Review text

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.NEWLINENEWLINENEWLINEThe 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.

Recommendations

• scientific article; zbMATH DE number 2102786
• scientific article; zbMATH DE number 1303607
• LATIN 2004: Theoretical Informatics
• Complexity of protein folding
• Solving hard problems by protein folding?

Cites work

• Complexity of protein folding
• Finding the lowest free energy conformation of a protein is an NP-hard problem: Proof and implications
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263191 (Why is no real title available?)
• Planar Formulae and Their Uses

Cited in

(10)

• Stochastic protein folding simulation in the three-dimensional HP-model
• The algorithmics of folding proteins on lattices.
• Solving hard problems by protein folding?
• Efficient segment folding is hard
• Folding proteins: how to set up an effcient metrics for dealing with complex systems
• The complexity of the stamp folding problem
• scientific article; zbMATH DE number 1303607 (Why is no real title available?)
• scientific article; zbMATH DE number 1759460 (Why is no real title available?)
• scientific article; zbMATH DE number 2102786 (Why is no real title available?)
• Algorithmic folding complexity

This page was built for publication: On the complexity of string folding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961626)