{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:11:11Z","timestamp":1794381071530,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_54","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"630-644","source":"Crossref","is-referenced-by-count":18,"title":["A $2^{O(n^{1-{1\\over d}}\\log n)}$ Time Algorithm for d-Dimensional Protein Folding in the HP-Model"],"prefix":"10.1007","author":[{"given":"Bin","family":"Fu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1089\/cmb.1997.4.275","volume":"4","author":"R. Agarwala","year":"1997","unstructured":"Agarwala, R., Batzoglou, S., Dancik, V., Decatur, S., Hannenhalli, S., Farach, M., Muthukrishnan, M., Skiena, S.: Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model. Journal of Computational Biology\u00a04, 275\u2013296 (1997)","journal-title":"Journal of Computational Biology"},{"issue":"2","key":"54_CR2","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/S0895480191198768","volume":"7","author":"N. Alon","year":"1990","unstructured":"Alon, N., Seymour, P., Thomas, R.: Planar Separator. SIAM J. Discr. Math.\u00a07(2), 184\u2013193 (1990)","journal-title":"SIAM J. Discr. Math."},{"key":"54_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/3-540-49481-2_7","volume-title":"Proceedings of 4th International conference on principle and practice of constrain programming","author":"R. Backofen","year":"1998","unstructured":"Backofen, R.: Constraint techniques for solving the protein structure prediction problem. In: Proceedings of 4th International conference on principle and practice of constrain programming. LNCS, pp. 72\u201386. Springer, Heidelberg (1998)"},{"key":"54_CR4","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1089\/cmb.1998.5.27","volume":"5","author":"B. Berger","year":"1998","unstructured":"Berger, B., Leighton, T.: Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. Journal of Computational Biology\u00a05, 27\u201340 (1998)","journal-title":"Journal of Computational Biology"},{"key":"54_CR5","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0022-2836(80)90289-2","volume":"138","author":"F.E. Cohen","year":"1980","unstructured":"Cohen, F.E., Sternberg, M.J.E.: On the prediction of protein structure: the significance of the root-mean-square deviation. J. Mol. Biol.\u00a0138, 321\u2013333 (1980)","journal-title":"J. Mol. Biol."},{"key":"54_CR6","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1089\/cmb.1998.5.423","volume":"5","author":"P. Crescenzi","year":"1998","unstructured":"Crescenzi, P., Goldman, D., Papadimitriou, C., Piccolboni, A., Yannakakis, M.: On the complexity of protein folding. Journal of computational biology\u00a05, 423\u2013465 (1998)","journal-title":"Journal of computational biology"},{"key":"54_CR7","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1002\/(SICI)1097-0134(19980701)32:1<52::AID-PROT7>3.0.CO;2-G","volume":"32","author":"U. Bastolla","year":"1998","unstructured":"Bastolla, U., Frauenkron, H., Gerstner, E., Grassberger, P.: Nadler, Testing a new Monte Carlo algorithm for protein folding. Protein: Structure, Function, and Genetics\u00a032, 52\u201366 (1998)","journal-title":"Protein: Structure, Function, and Genetics"},{"key":"54_CR8","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1093\/protein\/6.8.801","volume":"6","author":"A. Godzik","year":"1993","unstructured":"Godzik, A., Skolnick, J., Kolinski, A.: Regularities in interaction patterns of globular proteins. Protein Engineering\u00a06, 801\u2013810 (1993)","journal-title":"Protein Engineering"},{"key":"54_CR9","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0022-2836(92)90693-E","volume":"227","author":"A. Godzik","year":"1992","unstructured":"Godzik, A., Skonick, J., Kolinski, A.: A topology fingerprint approach to inverse protein folding problem. J. Mol. Biol.\u00a0227, 227\u2013238 (1992)","journal-title":"J. Mol. Biol."},{"key":"54_CR10","doi-asserted-by":"crossref","unstructured":"Hart, W.E., Istrail, S.: Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal. In: Proceedings 27th ACM symposium on the theory of computing (1995)","DOI":"10.1145\/225058.225106"},{"key":"54_CR11","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1126\/science.273.5275.595","volume":"273","author":"L. Holm","year":"1996","unstructured":"Holm, L., Sander, C.: Mapping the protein universe. Science\u00a0273, 595\u2013602 (1996)","journal-title":"Science"},{"key":"54_CR12","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1080\/08927029708024151","volume":"19","author":"M. Khimasia","year":"1997","unstructured":"Khimasia, M., Coveney, P.: Protein structure prediction as a hard optimization problem: The genetic algorithm approach. Molecular Simulation\u00a019, 205\u2013226 (1997)","journal-title":"Molecular Simulation"},{"key":"54_CR13","volume-title":"Proceedings of Engineering of Intelligent Systems","author":"N. Krasnogor","year":"1998","unstructured":"Krasnogor, N., Pelta, D., Lopez, P.M., Mocciola, P., De la Canal, E.: Genetic algorithms for the protein folding problem: A critical view. In: Alpaydin, C.F.E. (ed.) Proceedings of Engineering of Intelligent Systems, ICSC Academic Press, London (1998)"},{"key":"54_CR14","doi-asserted-by":"publisher","first-page":"3986","DOI":"10.1021\/ma00200a030","volume":"22","author":"K.F. Lau","year":"1989","unstructured":"Lau, K.F., Dill, K.A.: A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules\u00a022, 3986\u20133997 (1989)","journal-title":"Macromolecules"},{"key":"54_CR15","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1073\/pnas.87.2.638","volume":"87","author":"K.F. Lau","year":"1990","unstructured":"Lau, K.F., Dill, K.A.: Theory for protein mutability and biogenesis. Proc. Natl. Acad. Sci.\u00a087, 638\u2013642 (1990)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"54_CR16","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.: A separator theorem for planar graph. SIAM J. Appl. Math.\u00a036, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"issue":"7","key":"54_CR17","doi-asserted-by":"publisher","first-page":"3374","DOI":"10.1063\/1.1387478","volume":"115","author":"F. Liang","year":"2001","unstructured":"Liang, F., Wong, W.H.: Evolutionary Monte Carlo for Protein folding simulations. Journal of Chemical Physics\u00a0115(7), 3374\u20133380 (2001)","journal-title":"Journal of Chemical Physics"},{"key":"54_CR18","unstructured":"Newman, A.: A new algorithm for protein folding in the HP model. In: Proceedings 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 876\u2013884 (2002)"},{"key":"54_CR19","unstructured":"Patton, A., W.P.III, Goldman, E.: A standard ga approach to native protein conformation prediction. In: Proc 6th Intl Conf Genetic Algorithms, Morgan Kauffman, pp. 574\u2013581. Morgan Kaufmann, San Francisco (1995)"},{"key":"54_CR20","doi-asserted-by":"crossref","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J. Pach","year":"1995","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley-Interscience Publication, Hoboken (1995)"},{"key":"54_CR21","volume-title":"Proceedings of I-CONIP 1997","author":"A. Piccolboni","year":"1998","unstructured":"Piccolboni, A., Mauri, G.: Application of evolutionary algorithms to protein prediction. In: Kasabov, N.e.a. (ed.) Proceedings of I-CONIP 1997, Springer, Heidelberg (1998)"},{"key":"54_CR22","doi-asserted-by":"publisher","first-page":"1800","DOI":"10.1002\/pro.5560050906","volume":"5","author":"A.A. Rabow","year":"1996","unstructured":"Rabow, A.A., Scheraga, H.A.: Improved genetic algorithm for the protein folding problem by use of a cartesian combination operator. Protein Science\u00a05, 1800\u20131815 (1996)","journal-title":"Protein Science"},{"key":"54_CR23","doi-asserted-by":"publisher","first-page":"2418","DOI":"10.1063\/1.473791","volume":"106","author":"R. Ramakrishnan","year":"1997","unstructured":"Ramakrishnan, R., Ramachandran, B., Pekney, J.F.: A dynamic Monte Carlo algorithm for exploration of dense conformation spaces in heteropolymers. Journal of Chemical Physics\u00a0106, 2418 (1997)","journal-title":"Journal of Chemical Physics"},{"key":"54_CR24","doi-asserted-by":"crossref","unstructured":"Smith, W.D., Wormald, N.C.: Application of geometric separator theorems. In: FOCS 1998, pp. 232\u2013243 (1998)","DOI":"10.1109\/SFCS.1998.743449"},{"key":"54_CR25","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1038\/369248a0","volume":"369","author":"E. Sali","year":"1994","unstructured":"Sali, E., Shakhnovich, M.: Karplus, How does a protein fold? Nature\u00a0369, 248\u2013251 (1994)","journal-title":"Nature"},{"key":"54_CR26","unstructured":"Unger, U., Moult, J.: A Genetic algorithm for three dimensional protein folding simulations. In: Proc. 5th Intl Conf on Genetic Algorithms, pp. 581\u2013588 (1993)"},{"issue":"1","key":"54_CR27","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1006\/jmbi.1993.1258","volume":"231","author":"U. Unger","year":"1993","unstructured":"Unger, U., Moult, J.: Genetic algorithms for protein folding simulations. Journal of Molecular Biology\u00a0231(1), 75\u201381 (1993)","journal-title":"Journal of Molecular Biology"},{"key":"54_CR28","first-page":"2267","volume":"E48","author":"K. Yue","year":"1993","unstructured":"Yue, K., Dill, K.A.: Sequence-structure relationships in proteins and copolymers. Physical Review\u00a0E48, 2267\u20132278 (1993)","journal-title":"Physical Review"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T23:31:03Z","timestamp":1619998263000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_54","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b99859","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}