{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T01:40:41Z","timestamp":1790646041486,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540258667","type":"print"},{"value":"9783540319504","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11415770_32","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T03:44:50Z","timestamp":1278992690000},"page":"423-439","source":"Crossref","is-referenced-by-count":62,"title":["Rapid Protein Side-Chain Packing via Tree Decomposition"],"prefix":"10.1007","author":[{"given":"Jinbo","family":"Xu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"32_CR1","first-page":"314","volume-title":"Third International Conference on Intelligent Systems for Molecular Biology","author":"B. Rost","year":"1995","unstructured":"Rost, B.: TOPITS: Threading one-dimensional predictions into three-dimensional structures. In: Rawlings, C., Clark, D., Altman, R., Hunter, L., Lengauer, T., Wodak, S. (eds.) Third International Conference on Intelligent Systems for Molecular Biology, pp. 314\u2013321. AAAI Press, Cambridge (1995)"},{"key":"32_CR2","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1089\/cmb.1998.5.597","volume":"5","author":"Y. Xu","year":"1998","unstructured":"Xu, Y., Xu, D., Uberbacher, E.: An efficient computational method for globally optimal threadings. Journal of Computational Biology\u00a05, 597\u2013614 (1998)","journal-title":"Journal of Computational Biology"},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1093\/protein\/gzg081","volume":"16","author":"D. Kim","year":"2003","unstructured":"Kim, D., Xu, D., Guo, J., Ellrott, K., Xu, Y.: PROSPECT II: Protein structure prediction method for genome-scale applications. Protein Engineering\u00a016, 641\u2013650 (2003)","journal-title":"Protein Engineering"},{"key":"32_CR4","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1006\/jmbi.1999.2583","volume":"287","author":"D. Jones","year":"1999","unstructured":"Jones, D.: GenTHREADER: An efficient and reliable protein fold recognition method for genomic sequences. Journal of Molecular Biology\u00a0287, 797\u2013815 (1999)","journal-title":"Journal of Molecular Biology"},{"key":"32_CR5","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1006\/jmbi.2000.3741","volume":"299","author":"L. Kelley","year":"2000","unstructured":"Kelley, L., MacCallum, R., Sternberg, M.: Enhanced genome annotation using structural profiles in the program 3D-PSSM. Journal of Molecular Biology\u00a0299, 499\u2013520 (2000)","journal-title":"Journal of Molecular Biology"},{"key":"32_CR6","unstructured":"Alexandrov, N., Nussinov, R., Zimmer, R.: Fast protein fold recognition via sequence to structure alignment and contact capacity potentials. In: Biocomputing: Proceedings of 1996 Pacific Symposium (1996)"},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"2228","DOI":"10.1093\/bioinformatics\/bth232","volume":"20","author":"N. Ohsen von","year":"2004","unstructured":"von Ohsen, N., Sommer, I., Zimmer, R., Lengauer, T.: Arby: automatic protein structure prediction using profile-profile alignment and confidence measures. Bioinformatics\u00a020, 2228\u20132235 (2004)","journal-title":"Bioinformatics"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1006\/jmbi.2001.4762","volume":"310","author":"J. Shi","year":"2001","unstructured":"Shi, J., Tom, L.B., Kenji, M.: FUGUE: Sequence-structure homology recognition using environment-specific substitution tables and structure-dependent gap penalties. Journal of Molecular Biology\u00a0310, 243\u2013257 (2001)","journal-title":"Journal of Molecular Biology"},{"key":"32_CR9","volume-title":"Proceedings of the 27th Hawaii International Conference on System Sciences","author":"R. Lathrop","year":"1994","unstructured":"Lathrop, R., Smith, T.: A branch-and-bound algorithm for optimal protein threading with pairwise (contact potential) amino acid interactions. In: Proceedings of the 27th Hawaii International Conference on System Sciences. IEEE Computer Society Press, Los Alamitos (1994)"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0304-3975(98)00089-9","volume":"210","author":"T. Akutsu","year":"1999","unstructured":"Akutsu, T., Miyano, S.: On the approximation of protein threading. Theoretical Computer Science\u00a0210, 261\u2013275 (1999)","journal-title":"Theoretical Computer Science"},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1093\/bioinformatics\/16.12.1105","volume":"16","author":"W. Li","year":"2000","unstructured":"Li, W., Pio, F., Pawlowski, K., Godzik, A.: Saturated BLAST: detecting distant homology using automated multiple intermediate sequence BLAST search. Bioinformatics\u00a016, 1105\u20131110 (2000)","journal-title":"Bioinformatics"},{"key":"32_CR12","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1016\/0022-2836(89)90109-5","volume":"210","author":"N. Summers","year":"1989","unstructured":"Summers, N., Karplus, M.: Construction of side-chains in homology modelling: Application to the c-terminal lobe of rhizopuspepsin. Journal of Molecular Biology\u00a0210, 785\u2013811 (1989)","journal-title":"Journal of Molecular Biology"},{"key":"32_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0022-2836(91)90883-8","volume":"218","author":"L. Holm","year":"1991","unstructured":"Holm, L., Sander, C.: Database algorithm for generating protein backbone and sidechain coordinates from a C \u03b1 trace: Application to model building and detection of coordinate errors. Journal of Molecular Biology\u00a0218, 183\u2013194 (1991)","journal-title":"Journal of Molecular Biology"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1038\/356539a0","volume":"356","author":"J. Desmet","year":"1992","unstructured":"Desmet, J., Maeyer, M.D., Hazes, B., Laster, I.: The dead-end elimination theorem and its use in protein side-chain positioning. Nature\u00a0356, 539\u2013542 (1992)","journal-title":"Nature"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1002\/prot.10131","volume":"48","author":"J. Desmet","year":"2002","unstructured":"Desmet, J., Spriet, J., Laster, I.: Fast and accurate side-chain topology and energy refinement (faster) as a new method for protein structure optimization. Protein: Structure, Function and Genetics\u00a048, 31\u201343 (2002)","journal-title":"Protein: Structure, Function and Genetics"},{"key":"32_CR16","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1002\/(SICI)1097-0134(1999)37:3+<81::AID-PROT12>3.0.CO;2-R","volume":"3","author":"R.L. Dunbrack Jr.","year":"1999","unstructured":"Dunbrack Jr., R.L.: Comparative modeling of CASP3 targets using PSI-BLAST and SCWRL. Protein: Structure, Function and Genetics\u00a03, 81\u201387 (1999)","journal-title":"Protein: Structure, Function and Genetics"},{"key":"32_CR17","doi-asserted-by":"publisher","first-page":"2001","DOI":"10.1110\/ps.03154503","volume":"12","author":"A. Canutescu","year":"2003","unstructured":"Canutescu, A., Shelenkov, A., Dunbrack Jr., R.L.: A graph-theory algorithm for rapid protein side-chain prediction. Protein Science\u00a012, 2001\u20132014 (2003)","journal-title":"Protein Science"},{"key":"32_CR18","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1093\/protein\/11.11.991","volume":"11","author":"R. Samudrala","year":"1998","unstructured":"Samudrala, R., Moult, J.: Determinants of side chain conformational preferences in protein structures. Protein Engineering\u00a011, 991\u2013997 (1998)","journal-title":"Protein Engineering"},{"key":"32_CR19","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jmbi.2001.4865","volume":"311","author":"Z. Xiang","year":"2001","unstructured":"Xiang, Z., Honig, B.: Extending the accuracy limits of prediction for side-chain conformations. Journal of Molecular Biology\u00a0311, 421\u2013430 (2001)","journal-title":"Journal of Molecular Biology"},{"key":"32_CR20","doi-asserted-by":"publisher","first-page":"1268","DOI":"10.1006\/jmbi.1997.0926","volume":"267","author":"M. Bower","year":"1997","unstructured":"Bower, M., Cohen, F., Dunbrack Jr., R.L.: Prediction of protein side-chain rotamers from a backbone-dependent rotamer library: A new homology modeling tool. Journal of Molecular Biology\u00a0267, 1268\u20131282 (1997)","journal-title":"Journal of Molecular Biology"},{"key":"32_CR21","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1110\/ps.24902","volume":"11","author":"S. Liang","year":"2002","unstructured":"Liang, S., Grishin, N.: side-chain modelling with an optimized scoring function. Protein Science\u00a011, 322\u2013331 (2002)","journal-title":"Protein Science"},{"key":"32_CR22","unstructured":"Hong, E., Lozano-Perez, T.: Protein side-chain placement: probabilistic inference and integer programming methods. Technical report, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology (2004)"},{"key":"32_CR23","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Kingsford, C., Singh, M.: A semidefinite programming approach to side-chain positioning with new rounding strategies. Informs Journal on Computing, Special Issue in Computational Molecular Biology\/Bioinformatics, 86\u201394 (2004)","DOI":"10.1287\/ijoc.1040.0096"},{"key":"32_CR24","doi-asserted-by":"crossref","unstructured":"Kingsford, C.L., Chazelle, B., Singh, M.: Solving and analyzing side-chain positioning problems using linear and integer programming. Bioinformatics (2004)","DOI":"10.1093\/bioinformatics\/bti144"},{"key":"32_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/3-540-44696-6_10","volume-title":"Algorithms in Bioinformatics","author":"O. Eriksson","year":"2001","unstructured":"Eriksson, O., Zhou, Y., Elofsson, A.: Side chain-positioning as an integer programming problem. In: Gascuel, O., Moret, B.M.E. (eds.) WABI 2001. LNCS, vol.\u00a02149, pp. 128\u2013141. Springer, Heidelberg (2001)"},{"key":"32_CR26","unstructured":"Dukka, K., Tomita, E., Suzuki, J., Akutsu, T.: Protein side-chain packing problem: a maximum common edge-weight clique algorithmic approach. In: The Second Asia Pacific Bioinformatics Conference (2004)"},{"key":"32_CR27","unstructured":"Althaus, E., Kohlbacher, O., Lenhof, H., M\u00fcller, P.: A branch and cut algorithm for the optimal solution of the side-chain placement problem. Technical Report MPI-I-2000-1-001, Max-Planck-Institute f\u00fcr Informatik (2000)"},{"key":"32_CR28","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1006\/jmbi.1993.1170","volume":"230","author":"R.L. Dunbrack Jr.","year":"1993","unstructured":"Dunbrack Jr., R.L., Karplus, M.: Backbone-dependent rotamer library for proteins: Application to side-chain prediction. Journal of Molecular Biology\u00a0230, 543\u2013574 (1993)","journal-title":"Journal of Molecular Biology"},{"key":"32_CR29","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1093\/protein\/15.10.779","volume":"15","author":"N. Pierce","year":"2002","unstructured":"Pierce, N., Winfree, E.: Protein design is NP-hard. Protein Engineering\u00a015, 779\u2013782 (2002)","journal-title":"Protein Engineering"},{"key":"32_CR30","unstructured":"Akutsu, T.: NP-hardness results for protein side-chain packing. In: Miyano, S., Takagi, T. (eds.) Genome Informatics, vol.\u00a08, pp. 180\u2013186 (1997)"},{"key":"32_CR31","doi-asserted-by":"crossref","unstructured":"Sali, A., Blundell, T.: Comparative protein modelling by satisfaction of spatial restraints. Journal of Molecular Biology, 779\u2013815 (1993)","DOI":"10.1006\/jmbi.1993.1626"},{"key":"32_CR32","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1002\/(SICI)1097-0134(19981101)33:2<227::AID-PROT7>3.0.CO;2-F","volume":"33","author":"A. Leach","year":"1998","unstructured":"Leach, A., Lemon, A.: Exploring the conformational space of protein side chains using dead-end elimination and the A * algorithm. Protein: Structure, Function and Genetics\u00a033, 227\u2013239 (1998)","journal-title":"Protein: Structure, Function and Genetics"},{"key":"32_CR33","doi-asserted-by":"publisher","first-page":"1335","DOI":"10.1016\/S0006-3495(94)80923-3","volume":"66","author":"R. Goldstein","year":"1994","unstructured":"Goldstein, R.: Efficient rotamer elimination applied to protein side-chains and related spin glasses. Biophysical Journal\u00a066, 1335\u20131340 (1994)","journal-title":"Biophysical Journal"},{"key":"32_CR34","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.: Graph minors. II. algorithmic aspects of tree-width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"32_CR35","unstructured":"Koster, A., van Hoesel, S., Kolen, A.: Solving frequency assignment problems via tree-decomposition. Research Memoranda 036, Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization (1999), available at http:\/\/ideas.repec.org\/p\/dgr\/umamet\/1999036.html"},{"key":"32_CR36","doi-asserted-by":"crossref","unstructured":"Bach, F., Jordan, M.: Thin junction trees. In: Dietterich, T., Becker, S., Ghahramani, Z. (eds.) Advances in Neural Information Processing Systems (NIPS), vol.\u00a014 (2002)","DOI":"10.7551\/mitpress\/1120.003.0078"},{"key":"32_CR37","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D., Proskurowski, A.: Complexity of finding embedding in a k-tree. SIAM Journal on Algebraic and Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"32_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"G.L. Miller","year":"1997","unstructured":"Miller, G.L., Teng, S., Thurston, W., Vavasis, S.A.: Separators for sphere-packings and nearest neighbor graphs. Journal of ACM\u00a044, 1\u201329 (1997)","journal-title":"Journal of ACM"},{"key":"32_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-540-39890-5_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Berry","year":"2003","unstructured":"Berry, A., Heggernes, P., Simonet, G.: The minimum degree heuristic and the minimal triangulation process. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 58\u201370. Springer, Heidelberg (2003)"},{"key":"32_CR40","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1093\/bioinformatics\/16.9.815","volume":"16","author":"O. Kohlbacher","year":"2000","unstructured":"Kohlbacher, O., Lenhof, H.: BALL - rapid software prototyping in computational molecular biology. Bioinformatics\u00a016, 815\u2013824 (2000)","journal-title":"Bioinformatics"},{"key":"32_CR41","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D., Netanyahu, N., Silverman, R., Wu, A.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Journal of ACM\u00a045, 891\u2013923 (1998)","journal-title":"Journal of ACM"},{"key":"32_CR42","unstructured":"Mount, D., Arya, S.: ANN: a library for approximate nearest neighbor searching. In: 2nd CGC Workshop on Computational Geometry (1997)"},{"key":"32_CR43","unstructured":"Amir, E.: Efficient approximation for triangulation of minimum treewdith. In: 17th Conference on Uncertainty in Artificial Intelligence, UAI 2001 (2001)"},{"key":"32_CR44","doi-asserted-by":"crossref","unstructured":"Xu, J., Li, M., Lin, G., Kim, D., Xu, Y.: Protein threading by linear programming. In: Biocomputing: Proceedings of the 2003 Pacific Symposium, Hawaii, USA, pp. 264\u2013275 (2003)","DOI":"10.1142\/9789812776303_0025"},{"key":"32_CR45","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/S0219720003000186","volume":"1","author":"J. Xu","year":"2003","unstructured":"Xu, J., Li, M., Kim, D., Xu, Y.: RAPTOR: optimal protein threading by linear programming. Journal of Bioinformatics and Computational Biology\u00a01, 95\u2013117 (2003)","journal-title":"Journal of Bioinformatics and Computational Biology"}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11415770_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,28]],"date-time":"2024-03-28T08:04:14Z","timestamp":1711613054000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11415770_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540258667","9783540319504"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/11415770_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}