doi: 10.1142/s0219720008003308.
Fitting protein chains to cubic lattice is NP-complete
Affiliations
- PMID: 18324748
- DOI: 10.1142/s0219720008003308
Item in Clipboard
Fitting protein chains to cubic lattice is NP-complete
J Bioinform Comput Biol.
2008 Feb.
Abstract
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.
Similar articles
-
Generation and enumeration of compact conformations on the two-dimensional triangular and three-dimensional fcc lattices.J Chem Phys. 2007 Jul 28;127(4):044101. doi: 10.1063/1.2751169. J Chem Phys. 2007. PMID: 17672675
-
Protein structure-structure alignment with discrete Fréchet distance.J Bioinform Comput Biol. 2008 Feb;6(1):51-64. doi: 10.1142/s0219720008003278. J Bioinform Comput Biol. 2008. PMID: 18324745
-
Can molecular dynamics simulations help in discriminating correct from erroneous protein 3D models?BMC Bioinformatics. 2008 Jan 7;9:6. doi: 10.1186/1471-2105-9-6. BMC Bioinformatics. 2008. PMID: 18179702 Free PMC article.
-
An introduction to modeling structure from sequence.Curr Protoc Bioinformatics. 2006 Oct;Chapter 5:Unit 5.1. doi: 10.1002/0471250953.bi0501s15. Curr Protoc Bioinformatics. 2006. PMID: 18428765 Review.
-
Predicting 3D structures of protein-protein complexes.Curr Pharm Biotechnol. 2008 Apr;9(2):57-66. doi: 10.2174/138920108783955209. Curr Pharm Biotechnol. 2008. PMID: 18393862 Review.
Cited by
-
LocalMove: computing on-lattice fits for biopolymers.Nucleic Acids Res. 2008 Jul 1;36(Web Server issue):W216-22. doi: 10.1093/nar/gkn367. Epub 2008 Jun 13. Nucleic Acids Res. 2008. PMID: 18556754 Free PMC article.
-
A Multi-Objective Approach for Protein Structure Prediction Based on an Energy Model and Backbone Angle Preferences.Int J Mol Sci. 2015 Jul 3;16(7):15136-49. doi: 10.3390/ijms160715136. Int J Mol Sci. 2015. PMID: 26151847 Free PMC article.
-
Producing high-accuracy lattice models from protein atomic coordinates including side chains.Adv Bioinformatics. 2012;2012:148045. doi: 10.1155/2012/148045. Epub 2012 Aug 15. Adv Bioinformatics. 2012. PMID: 22934109 Free PMC article.
-
How good are simplified models for protein structure prediction?Adv Bioinformatics. 2014;2014:867179. doi: 10.1155/2014/867179. Epub 2014 Apr 29. Adv Bioinformatics. 2014. PMID: 24876837 Free PMC article.
Publication types
MeSH terms
Substances
LinkOut - more resources
Full Text Sources
Miscellaneous
