Bonnie Berger
- 1.P~ AgarwMa, S. Bstzoglou, V. Dan~, S. Decatur, M. Fa~ach, S. }:{asmenh~li, S. SMena, and S. Muth~hnan. Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model J. Computational BioL, 4(3):275-296, Fail 1997.Google Scholar
Cross Ref
- 2.T. Akutsn and S. Miyano. On the approximation of protein threading. In Proc. First Annual Int. Conf. on Computational Molecular BioL (RE- COdl~B), pages 3-8, Santa Fe, NM, jan 1997. ACM. Google ScholarDigital Library
- 3.B. Berger and T. Leighton. Protein folding in the hyd~ophobic-hydropMlic (HP) model is NP- complete. J. Computational BioL, Spiing 1998. In press.Google ScholarCross Ref
- 4.J. D. Bryngelson, J. N. Onuchic, N. D. Socci, and P. G. Wolynes. F,,nnels, pathways, and the energy landscape of protein folding: a synthesis. PROTEINS: Structure, Function, and Genetics, 21:167-195, 1995.Google Scholar
- 5.P. CrescenzL D. Goldman, C. Papadimitfiou, A. Piccolboni, and M. Yunna. On the compleMty of protein folding. In Proc. 2nd Annual Int. Conf. on Computational Molecular Biology (RECOMB), New York City, NY, March 1998. ACM. To appear. Google ScholarDigital Library
- 6.K. Dill Theory for the folding and stability of globular proteins. Biochemistry, 24:1501-1809, 1985.Google ScholarCross Ref
- 7.K. Dill, S. Bromberg, K. Yue, K. Fiebig, D. Yee, P. Thomas, and H. Chan. Pl:mdples of protein folding: A perspective from simple exact models. Protein Science, 4:561-602, 1995.Google ScholarCross Ref
- 8.A. Fraenkel. Deexponentializing complex computational mathematical problems using physical or biological systems. Technical Report CS90-30, Weizmann Inst. of Science, Dept. of Applied Math and Computer Science, 1990.Google Scholar
- 9.A. Fraenkel. Complexity of protein folding. Bull. Math BioL, 55:1199-1210, 1993.Google ScholarCross Ref
- 10.A. $. Fraenkel. Protein folding, spin glass and computational complexity. In Third Annual DIMACS Workshop on DNA Based Computers, Philadelphia, PA, June 1997. To appear in proceedings as an invited paper.Google Scholar
- 11.M. Garey and D. Johnson. Computers and Intractability. Freeman, New York, 1979. Google ScholarDigital Library
- 12.W. Hart and S. Istrail. Fast protein folding in the hydrophobic-hydrophilic model within three-eighths of optimal. Y. Computational Biol., 3(1):53-96, Spring 1996.Google ScholarCross Ref
- 13.W. Hart and S. Isf, rail. Robust proofs of NP- hardness for protein folding: GenerM lattices and energy potentials. J. Computational Biol., 4(1):1- 22, Spring 1997.Google ScholarCross Ref
- 14.W. E. Hart. On the computational complexity of sequence design problems. In Proc. First Annual Int. Conf. on Computational Molecular Biology (RECOMB), pages 128-136, Santa Fe, NM, jan 1997. ACM. Google ScholarDigital Library
- 15.W. E. Hart and S. istrail. Lattice and off-lattice side chain models of protein folding: Linear time structure prediction better than In Proc. First Annual Int. Conf. on Computational Molecular Biology (RECOMB), pages 137-146, Santa Fe, NM, jan 1997. AOM. Google ScholarDigital Library
- 16.R. It. Lathrop. The protein threading problem with sequence amino acid interaction preferences is npcomplete. Protein Engineering, 7:1059-1068, 1994.Google ScholarCross Ref
- 17.T. Leighton. Introduction to Parallel Algorithms and Architechtures: Arrays. Trees ~ Hypercubes, chapter Arrays and Trees, page 190. Morgan Kaufmann, San Mateo, CA, 1992. Google ScholarDigital Library
- 18.T. Leighton and A. Rosenberg. Three-dimensional circuit layouts. SIAM J. Computing, 15(3):793- 813, 1986. Google ScholarDigital Library
- 19.A. Nayak, A. Sinclair, and U. Zwick. Spatial codes and the hardness of string folding problems. In Proceedin#s of the Ninth Annual A CM-SIAM Symposiam on Discrete Algorithms, Philadelphia, January 1998. ACM/SIAM. To appear. Google ScholarDigital Library
- 20.J. Ngo and J. Marks. Computatinal complexity of a problem in molecular structure prediction. Protein Engineering, 5:313-321, 1992.Google ScholarCross Ref
- 21.J. Ngo, J. Marks, and M. Kaxplus. The Protein Folding Problem and Tertiary Structure Prediction, chapter Computational complexity, protein structure prediction, and the Levinthal paradox. Birkhanser, Basel, 1994. Edited by K.M. Merz and S.M. LeGrand.Google Scholar
- 22.M. Paterson and T. Przytycka. On the complexity of string folding. Discrete Applied Mathematics, 71:217-230, 1996. Google ScholarDigital Library
- 23.IL Unger and J. Moult. Finding the lowest free energy conformatoin of a protein is an np-hard prblem:proof and implications. Bull Math. BioL, 55:1183-1198, 1993.Google ScholarCross Ref
Index Terms
- Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete
Recommendations
Protein folding potential functions
HICSS '95: Proceedings of the 28th Hawaii International Conference on System SciencesThere has been a great deal of activity recently on approaches to the calculation of protein folding using specially devised empirical potential functions. We have developed one such function that solves the protein structure recognition problem: given ...
Protein Structure Classification Based on Conserved Hydrophobic Residues
Protein folding is frequently guided by local residue interactions that form clusters in the protein core. The interactions between residue clusters serve as potential nucleation sites in the folding process. Evidence postulates that the residue ...
An Analytical Study of NP-Hard Protein Folding Problems
ICICA '14: Proceedings of the 2014 International Conference on Intelligent Computing ApplicationsProtein folding problem is a Non deterministic Polynomial hard problem. Proteins are of different types, whereas each protein plays an important role in the living cells. Every protein has a unique structure and function. The unique structure is formed ...
Comments