On the approximation of protein threading

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the approximation of protein threading

Full text

Pdf (708 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: 3 - 8

Year of Publication: 1997

ISBN:0-89791-882-7

Authors

Tatsuya Akutsu	Human Genome Center, Institute of Medical Science, University of Tokyo, 4-6-1 Shirokanedai, Minato-ku, Tokyo 108 Japan
Satoru Miyano	Human Genome Center, Institute of Medical Science, University of Tokyo, 4-6-1 Shirokanedai, Minato-ku, Tokyo 108 Japan

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): 4, Downloads (12 Months): 16, Citation Count: 3

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.267523 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. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, "Proof verification and hardness of approximation algorithms," Proc. $$rd IEEE $yrnp. Foundations of Computer Science, pp. 14-23, 1992.
	2	J. U. Bowie, R. Lfithy and D. Eisenbetg, "A method to identify protein sequences that fold into a known threedimensional structures," Science, Vol. 253, pp. 164-170, 1991.
	3	C. Branden and J. Tooze, Introduction to Protein Structure, Garland Publishing, 1991.
	4	S. H. Bryant and C. E. Lawrence, "An empirical energy function for threading protein sequence through the folding motif," PROTEINS: Structure, Function, and Genetics, Vol. 16, pp. 92-112, 1993.
	5	C. Chothia, "One thousand families for the molecular biologist," Nature, Vol. 357, pp. 543-544, 1992.
	6	A. Godzik and J. Skolnick, "Sequence-structure matching in globular proteins: apphcation to supersecondary and tertiary structure determination," Proc. National Academy of Science USA, Vol. 89, pp. 12098-12102, 1992.
	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	G. Kortsarz and D. Peleg, "On choosing a dense subgraph," Proc. 3jth IEEE Syrup. Foundations of Computer Science, pp. 692-701, 1993.
	9	R. H. Lathrop, "The protein threading problem with sequence amino acid interaction preferences is NP- complete," Protein Engineering, Vol. 7, pp. 1059-1068, 1994.
	10	R. H. Lathrop and T. F. Smith, "A branch-and-bound algorithm for optimal protein threading with pairwise (contact potential) amino acid interactions," Proc. ~Tth Annual Hawaii International Conference on System Sciences, Vol. 5, pp. 365-374, 1994.
	11	David Maier, The Complexity of Some Problems on Subsequences and Supersequences, Journal of the ACM (JACM), v.25 n.2, p.322-336, April 1978 [doi>10.1145/322063.322075]
	12	T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms, Elsevier Science, 1988.
	13	C. H. Papadimitriou and M. Yannakakis, "Optimization, approximation, and complexity classes," J. Computer and System Sciences, Vol. 43, pp. 425-440, 1991.
	14	H. Tashimo and T. Akutsu, "Learning score function for protein threading using linear programming," Technical Report (in Japanese), MPS-8-4, information Processing Society of Japan, 1996.

CITED BY 3

	Richard H. Lathrop, An anytime algorithm for gapped block protein threading with pair interactions, Proceedings of the third annual international conference on Computational molecular biology, p.238-249, April 11-14, 1999, Lyon, France
	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
	Rolf Backofen , David Gilbert, Bioinformatics and Constraints, Constraints, v.6 n.2-3, p.141-156, June 2001