Fitting protein chains to cubic lattice is NP-complete.
It is known that folding a protein chain into a cubic lattice is an NP-complete problem. We consider a seemingly easier problem: given a three-dimensional (3D) fold of a protein chain (coordinates of its C(alpha) atoms), we want to find the closest lattice approximation of this fold. This problem has been studied under names such as "lattice approximation of a protein chain", "the protein chain fitting problem", and "building of protein lattice models". We show that this problem is NP-complete for the cubic lattice with side close to 3.8 A and coordinate root mean square deviation.
Manuch
Ján
J
School of Computing Science, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada. jmanuch@sfu.ca
Gaur
Daya Ram
DR
D000595:Amino Acid Sequence; D003198:Computer Simulation; D008956:Models, Chemical; D008958:Models, Molecular; D008969:Molecular Sequence Data; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry* / Q000648:ultrastructure*; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*
D011506:Proteins