On the complexity of protein folding (abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of protein folding (abstract)

Full text

Pdf (236 KB)

Source

Annual Conference on Research in Computational Molecular Biology archive
Proceedings of the second annual international conference on Computational molecular biology table of contents

New York, New York, United States

Pages: 61 - 62

Year of Publication: 1998

ISBN:0-89791-976-9

Authors

Pierluigi Crescenzi
Deborah Goldman
Christos Papadimitriou
Antonio Piccolboni
Mihalis Yannakakis

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 20, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/279069.279089 What is a DOI?

REFERENCES

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	B. Berger, F. T. Leighton, manuscript submitted to J. Mol. BioL, July 1997. Extended abstract appearing in this volume.
	2	Pierluigi Crescenzi , Deborah Goldman , Christos Papadimitriou , Antonio Piccolboni , Mihalis Yannakakis, On the complexity of protein folding (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.597-603, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276875]
	3	H. S. Chart, K. A. Dill. The protein folding problem. Physics Today (1993), pp. 24-32.
	4	K. A. Dill. Dominant forces in protein folding. Biochemistry 29 (1990), pp. 7133-7155.
	5	K. A. Dill, S. Bromberg, K. Yue, K. Fiebig, D. P. Yee, P. D. Thomas, H. S. Chart. Principles of protein folding- A perspective from simple exac~ models. Protein Science 4 (1995), pp. 561-602.
	6	A. S. Fraenkel. Complexity of protein folding. Bulletin of Mathematical Biology 55 (1993), pp. 1199-1210.
	7	William E. Hart , Sorin Istrail, Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.157-168, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225106]
	8	J. King. Deciphering the rules of protein folding. Chemical Engineering News 67 (1989), pp. 32-54.
	9	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
	10	J. T. Ngo, J. Marks, M. Karplus. Computational complexity, protein structure prediction, and the Levinthal paradox. In The protein .folding problem and tertiary structure prediction, edited by K. M. Merz and S. M. Le Grand, Birkhauser, Boston, 1994.
	11	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]
	12	Luca Trevisan, When Hamming meets Euclid: the approximability of geometric TSP and MST (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.21-29, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258541]
	13	R. Unger, J. Moult. Finding ~he lowes~ free energy conformation of a protein is an NP-hard problem: proof and implications. Bulletin of Mathematical Biology 55 (1993), pp. 1183-1198.

CITED BY 7

	Bonnie Berger , Tom Leighton, Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete, Proceedings of the second annual international conference on Computational molecular biology, p.30-39, March 22-25, 1998, New York, New York, United States
	Giancarlo Mauri , Giulio Pavesi , Antonio Piccolboni, Approximation algorithms for protein folding prediction, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.945-946, January 17-19, 1999, Baltimore, Maryland, United States
	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
	Alantha Newman, A new algorithm for protein folding in the HP model, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.876-884, January 06-08, 2002, San Francisco, California
	Volker Heun, Approximate protein folding in the HP side chain model on extended cubic lattices, Discrete Applied Mathematics, v.127 n.1, p.163-177, April 2003
	Rolf Backofen , Sebastian Will, A Constraint-Based Approach to Fast and Exact Structure Prediction in Three-Dimensional Protein Models, Constraints, v.11 n.1, p.5-30, January 2006
	Rolf Backofen , David Gilbert, Bioinformatics and Constraints, Constraints, v.6 n.2-3, p.141-156, June 2001