On the computational complexity of sequence design problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the computational complexity of sequence design problems

Full text

Pdf (992 KB)

Source

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

Santa Fe, New Mexico, United States

Pages: 128 - 136

Year of Publication: 1997

ISBN:0-89791-882-7

Author

William E. Hart

Sandia National Laboratries, P.O. Box 5800, Albuquerque, NM

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
DOE : Department of Energy

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 9, Citation Count: 4

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/267521.267539 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	S. Bromberg and K. A. Dill. Side chain entropy and packing in proteins. Prot. Sci., pages 997-1009, 1994.
	2	J. M. Deutsch and T. Kurosky. New algorithm for protein design. Physical Review Letters, 76(2):323-326, 1996.
	3	K. A. Dill, S. Bromberg, K. Yue, K. M. Fiebig, D. P. Yee, P. D. Thomas, and H. S. Chan. Principles of protein folding: A perspective from simple exact models. Prot. Sci., 4:861-602, 1995.
	4	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
	5	S. Kamtekar, J. M. Schiffer, H. Xiong, J. M. Babik, and M. H. Hecht. Science, 262:1680-1685, 1993.
	6	T. Kurosky and J. M. Deutsch. Design of copolymeric materials. J. Phys. A, 27:L387-L393, 1995.
	7	K. F. Lau and K. A. Dill. A lattice statistical mechanics model of the conformation and sequence spaces of proteins. Macromolecules, 22:3986-3997, 1989.
	8	E. I. Shakhnovich and A. M. Gutin. Engineering of stable and fast-folding sequences of model proteins. Proc. Natl. Acad. Sci., 90:7195-7199, 1993.
	9	S. Sun, R. Brem, H. S. Chan, and K. A. Dill. Designing amino acid sequences to fold with good hydrophobic cores. Protein Engineering, 9(1), 1996. (in press).
	10	K. Yue and K. A. Dill. Inverse protein folding problem: Designing polymer sequences. Proc. Natl. A cad. Sci. USA, 89:4163-7, 1992.

CITED BY 4

	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
	Jon M. Kleinberg, Efficient algorithms for protein sequence design and the analysis of certain evolutionary fitness landscapes, Proceedings of the third annual international conference on Computational molecular biology, p.226-237, April 11-14, 1999, Lyon, France
	Piotr Berman , Bhaskar DasGupta , Dhruv Mubayi , Robert Sloan , György Turán , Yi Zhang, The inverse protein folding problem on 2D and 3D lattices, Discrete Applied Mathematics, v.155 n.6-7, p.719-732, April, 2007
	Rolf Backofen , David Gilbert, Bioinformatics and Constraints, Constraints, v.6 n.2-3, p.141-156, June 2001