It is known that folding a protein chain into the cubic lattice is an NP-complete problem. We consider a seemingly easier problem, given a 3D fold of a protein chain (coordinates of its C_alpha atoms), we want to find the closest lattice approximationof this fold. This problem has been studied under names such as "lattice approximation of a protein chain", "the protein chain fitting problem" and "building protein lattice models". We show that this problem is NP-complete for the cubic lattice with side 3.8A and the coordinate root mean-square deviation.
展开▼
