Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	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.
	2	Tatsuya Akutsu , Satoru Miyano, On the approximation of protein threading, Proceedings of the first annual international conference on Computational molecular biology, p.3-8, January 20-23, 1997, Santa Fe, New Mexico, United States [doi>10.1145/267521.267523]
	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.
	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.
	5	Pierluigi Crescenzi , Deborah Goldman , Christos Papadimitriou , Antonio Piccolboni , Mihalis Yannakakis, On the complexity of protein folding (abstract), Proceedings of the second annual international conference on Computational molecular biology, p.61-62, March 22-25, 1998, New York, New York, United States [doi>10.1145/279069.279089]
	6	K. Dill Theory for the folding and stability of globular proteins. Biochemistry, 24:1501-1809, 1985.
	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.
	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.
	9	A. Fraenkel. Complexity of protein folding. Bull. Math BioL, 55:1199-1210, 1993.
	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.
	11	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	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.
	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.
	14	William E. Hart, On the computational complexity of sequence design problems, Proceedings of the first annual international conference on Computational molecular biology, p.128-136, January 20-23, 1997, Santa Fe, New Mexico, United States [doi>10.1145/267521.267539]
	15	William E. Hart , Sorin Istrail, Lattice and off-lattice side chain models of protein folding (extended abstract): linear time structure prediction better than 86% of optimal, Proceedings of the first annual international conference on Computational molecular biology, p.137-146, January 20-23, 1997, Santa Fe, New Mexico, United States [doi>10.1145/267521.267540]
	16	R. It. Lathrop. The protein threading problem with sequence amino acid interaction preferences is npcomplete. Protein Engineering, 7:1059-1068, 1994.
	17	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	18	Frank Thomson Leighton , Arnold L Rosenberg, Three dimensional circuit layouts, SIAM Journal on Computing, v.15 n.3, p.793-813, August 1986 [doi>10.1137/0215057]
	19	Ashwin Nayak , Alistair Sinclair , Uri Zwick, Spatial codes and the hardness of string folding problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.639-648, January 25-27, 1998, San Francisco, California, United States
	20	J. Ngo and J. Marks. Computatinal complexity of a problem in molecular structure prediction. Protein Engineering, 5:313-321, 1992.
	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.
	22	Mike Paterson , Teresa Przytycka, On the complexity of string folding, Discrete Applied Mathematics, v.71 n.1-3, p.217-230, Dec. 5, 1996 [doi>10.1016/S0166-218X(96)00065-0]
	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.